题目描述
难度分:1600
输入T(≤104)表示T组数据。所有数据的n之和≤2×105。
每组数据输入n(1≤n≤2×105)和长为n的数组a(1≤a[i]≤n)。
枚举n的所有因子k,做如下计算:
把a分成nk段,每段长度均为k。如果存在一个≥2的整数m,使得所有a[i]%m后,这nk个段都相同,那么得分加一。
比如[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(√n)预处理出n的所有因子k,然后对于每个k求答案,看看这个k能不能找到一个合法的m。
对于一个指定的k,每个元素a[i]和a[i−k]相等属于同一个模系就可以了,即a[i]+x×m=a[i−k]+y×m,|a[i]−a[i−k]|是m的倍数。只要求出所有i∈[k+1,n]对应|a[i]−a[i−k]|的最大公约数即可(初始化这个最大公约数为0)。如果这个最大公约数>1,那它就是m,可以得分;如果这个最大公约数是0,说明数组a是个常数数列,随便哪个m都行,也能得分。所以只要gcd≠1就能得分。
复杂度分析
时间复杂度
预处理出所有的k时间复杂度为√n。对于每个k,需要遍历i∈[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)<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;
}