题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。

枚举$n$的所有因子$k$，做如下计算：

把$a$分成$\frac{n}{k}$段，每段长度均为$k$。如果存在一个$\geq 2$的整数$m$，使得所有$a[i] \% m$后，这$\frac{n}{k}$个段都相同，那么得分加一。

比如$[1,6,3,5,6,7]$在$k=3,m=4$的时候，可以得到两个一样的段$[1,2,3],[1,2,3]$。

输出总得分。注意每个$k$只能算一次得分。即对于同一个$k$，如果有多个$m$满足要求，也只计入$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

输出样例

2
1
2
4
4
1
2
1

算法

数论

先$O(\sqrt{n})$预处理出$n$的所有因子$k$，然后对于每个$k$求答案，看看这个$k$能不能找到一个合法的$m$。

对于一个指定的$k$，每个元素$a[i]$和$a[i-k]$相等属于同一个模系就可以了，即$a[i]+x \times m=a[i-k]+y \times m$，$|a[i]-a[i-k]|$是$m$的倍数。只要求出所有$i \in [k+1,n]$对应$|a[i]-a[i-k]|$的最大公约数即可（初始化这个最大公约数为$0$）。如果这个最大公约数$\gt 1$，那它就是$m$，可以得分；如果这个最大公约数是$0$，说明数组$a$是个常数数列，随便哪个$m$都行，也能得分。所以只要$gcd \neq 1$就能得分。

复杂度分析

时间复杂度

预处理出所有的$k$时间复杂度为$\sqrt{n}$。对于每个$k$，需要遍历$i \in [k+1,n]$，时间复杂度为$O(n)$；每次要计算最大公约数，而$a$的值域就是$[1,n]$，时间复杂度为$O(logn)$；这样算的话对于某个给定的$k$，时间复杂度似乎为$O(nlogn)$，但实际上会比这个量级小很多，因为最大公约数是越算越小的，从$n$变到$1$最多也只会进行$O(logn)$次辗转相除法，变成$1$之后就不再会执行辗转相除法，所以把这一步近似看做$O(n)$。

最后$k$的个数在$200000$以内最多为$240$个，所以可以把算法的整体时间复杂度看做$O(240n)$。

空间复杂度

所有因子$k$都要存入到一个数组$factors$中，空间消耗是$O(240)$，而辗转相除法递归深度最多为$O(logn) \lt 18$。所以瓶颈在于$factors$，额外空间复杂度为$O(240)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
int t, n, a[N];

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        vector<int> factors;
        for(int k = 2; k <= n/k; k++) {
            if(n % k == 0) {
                factors.push_back(k);
                if(k != n/k) {
                    factors.push_back(n/k);
                }
            }
        }
        int ans = 1;    // k=n时是一分
        if(n > 1) factors.push_back(1);
        for(int k: factors) {
            int m = 0;
            for(int i = k + 1; i <= n; i++) {
                m = __gcd(m, abs(a[i] - a[i - k]));
            }
            if(m != 1) ans++;
        }
        printf("%d\n", ans);
    }
    return 0;
}