CF1920C Partitioning the Array

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 可以获得一分。 请你帮助 Allen 计算他能获得的分数。

每个测试包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$）——数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq n$）——数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示 Allen 能获得的分数。

在第一个测试用例中，$k=2$ 可以获得一分，因为 Allen 可以选择 $m=2$，此时两个子数组都变为 $[1, 0]$。$k=4$ 也可以获得一分，因为无论 Allen 选择什么 $m$，只有一个子数组，因此所有子数组都相同。 在第二个测试用例中，Allen 可以在 $k=3$ 时获得一分，此时 $m$ 的选择无关紧要。 由 ChatGPT 4.1 翻译