← 返回题目列表

Codeforces · 1920/C

C. 对数组进行分区

中文机器翻译题面 查看原题

Allen 有一个数组 $$$a_1, a_2,\ldots,a_n$$$。对于每个作为 $$$n$$$ 约数的正整数 $$$k$$$,Allen 执行以下操作:

- 他将数组划分为 $$$\frac{n}{k}$$$ 长度为 $$$k$$$ 的不相交子数组。换句话说,他将数组划分为以下子数组: $$$$$$[a_1,a_2,\ldots,a_k],[a_{k+1}, a_{k+2},\ldots,a_{2k}],\ldots,[a_{n-k+1},a_{n-k+2},\ldots,a_{n}]$$$$$$
- 如果存在某个正整数 $$$m$$$ ($$$m \geq 2$$$),那么如果他将数组中的每个元素替换为除以 $$$m$$$ 后的余数,那么所有子数组都将相同,Allen 将获得一分。

帮助艾伦找到他将获得的分数。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2\cdot10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2,\ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 艾伦将获得的分数。

示例

输入 #1

8
4
1 2 1 4
3
1 2 3
5
1 1 1 1 1
6
1 3 1 1 3 1
6
6 2 6 2 2 2
6
2 6 3 6 6 6
10
1 7 5 1 4 3 1 3 1 4
1
1

输出 #1

2
1
2
4
4
1
2
1

注意

在第一个测试用例中,$$$k=2$$$ 得分,因为 Allen 可以选择 $$$m = 2$$$ 并且两个子数组都等于 $$$[1, 0]$$$。 $$$k=4$$$ 也获得一分,因为无论 $$$m$$$ Allen 选择什么,都只会有一个子数组,因此所有子数组都是相等的。

在第二个测试用例中,Allen 通过 $$$k=3$$$ 获得了 $$$1$$$ 点,其中他对 $$$m$$$ 的选择并不重要。