思维1350B · Orac and Models
商店里有 n 个模型，编号从 1 到 n，大小分别为 s_1, s_2, …, s_n。
Orac 会买其中一些模型，并按编号递增的顺序排列它们（即按索引，而不是按大小）。
Orac 认为得到的排列是美丽的，如果对于任意两个相邻的模型，其索引分别为 i_j 和 i_{j+1}（注意 i_j < i_{j+1}，因为 Orac 已正确排列它们），都有 i_{j+1} 能被 i_j 整除，且 s_{i_j} < s_{i_{j+1}}。
例如，对于 6 个大小分别为 {3, 6, 7, 7, 7, 7} 的模型，他可以买索引为 1、2 和 6 的模型，得到的排列将是美丽的。另外注意，恰好只有一个模型的排列也被认为是美丽的。
Orac 想知道他最多能买多少个模型，并且他可能会多次询问你这些问题。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
第一行包含一个整数 t\ (1 ≤ t≤ 100)：询问次数。
每次询问包含两行。第一行包含一个整数 n\ (1≤ n≤ 100\,000)：商店中模型的数量，第二行包含 n 个整数 s_1,…,s_n\ (1≤ s_i≤ 10^9)：模型的大小。
保证所有 n 的总和至多为 100\,000。
输出
输出 t 行，第 i 行应包含 Orac 在第 i 次询问中最多能买到的模型数量。
样例
输入
4
4
5 3 4 6
7
1 4 2 3 6 4 9
5
5 4 3 2 1
1
9
输出
2
3
1
1
提示
在第一次询问中，例如，Orac 可以买索引为 2 和 4 的模型，排列将是美丽的，因为 4 能被 2 整除，且 6 大于 3。通过枚举，我们可以很容易地发现不存在包含超过两个模型的美丽排列。
在第二次询问中，Orac 可以买索引为 1、3 和 6 的模型。通过枚举，我们可以很容易地发现不存在包含超过三个模型的美丽排列。
在第三次询问中，不存在包含超过一个模型的美丽排列。
提示
难度 1400 · dp, math, number theory
构造1753A1 · Make Nonzero Sum (easy version)
这是问题的简单版本。区别在于，在这个版本中数组不能包含零。只有当你解决了问题的两个版本时，才能进行 hack。
给定一个由整数 -1 和 1 组成的数组 [a_1, a_2, … a_n]。你需要将这个数组划分为一组段 [l_1, r_1], [l_2, r_2], …, [l_k, r_k]，满足以下性质：
· 记第 i 段所有元素的交错和为 s_i：s_i = a_{l_i} - a_{l_i+1} + a_{l_i+2} - a_{l_i+3} + … ± a_{r_i}。例如，数组 [1, 0, -1, 1, 1] 中段 [2, 4] 的元素的交错和等于 0 - (-1) + 1 = 2。
· 划分中所有段的 s_i 之和应等于零。
注意，每个 s_i 不必等于零，这个性质是关于划分中所有段的 s_i 之和。
段集合 [l_1, r_1], [l_2, r_2], …, [l_k, r_k] 被称为长度为 n 的数组 a 的一个划分，如果 1 = l_1 ≤ r_1, l_2 ≤ r_2, …, l_k ≤ r_k = n 且对于所有 i = 1, 2, … k-1 有 r_i + 1 = l_{i+1}。换句话说，数组的每个元素必须恰好属于一个段。
你需要构造给定数组的具有上述性质的划分，或者确定这样的划分不存在。
注意，不需要最小化划分中的段数。
输入 / 输出 / 样例（含数据范围）· 不写代码可以跳过
输入
每个测试包含多个测试数据。第一行包含测试数据的数量 t（1 ≤ t ≤ 10\,000）。测试数据的描述如下。
每个测试数据的第一行包含一个整数 n（1 ≤ n ≤ 200\,000）——数组 a 的长度。
每个测试数据的第二行包含 n 个整数 a_1, a_2, …, a_n（a_i 是 -1 或 1）——给定数组的元素。
保证所有测试数据的 n 之和不超过 200\,000。
输出
对于每个测试数据，如果所需的划分不存在，输出 -1。否则，输出一个整数 k——划分中的段数。
然后在接下来的 k 行中的第 i 行输出两个整数 l_i 和 r_i——第 i 段的描述。应满足以下条件：
· 对于从 1 到 k 的每个 i，l_i ≤ r_i。
· 对于从 1 到 (k - 1) 的每个 i，l_{i + 1} = r_i + 1。
· l_1 = 1, r_k = n。
如果数组有多个正确的划分，输出其中任意一个。
样例
输入
4
4
1 1 1 1
6
-1 1 1 1 1 1
3
1 -1 1
1
1
输出
1
1 4
2
1 3
4 6
-1
-1
提示
在第一个测试数据中，我们可以构造一个长度为 4 的单段划分。该段的和将等于 1 - 1 + 1 - 1 = 0。
在第二个测试数据中，我们可以构造两个长度为 3 的段的划分。第一段的和将等于 -1 -1 + 1 = -1，第二段的和：1 - 1 + 1 = 1。因此，总和将等于 -1 + 1 = 0。
在第三个和第四个测试数据中可以证明不存在所需的划分。
提示
难度 1300 · constructive algorithms, dp, greedy