cf919Div2C题题目总结

Problem - C - Codeforces

这道题其实是一道数学题。

先看第一个变量，也就是我们要求的答案k的数量，但看k是很好确定它的限制条件的，要想均匀分成k份，n%k必须为0，有了k，我们再来看m，对于a(1)和a(k+1),要使它们除以m后相同，肯定满足一下式子a(1)=x1*m1+n1，a(k+1)=y1*m1+n1对于其它的对应的a也是一样的，a(2)=x2*m2+n2，a(k+2)=y2*m2+n2……，那么只要知道m1是否等于m2就可以了吧，如果m1等于m2就说明m存在，在有n1和n2的阻碍下，显然算不出m，不妨将两者相减a(1)-a(k+1)=(x1-y1)*m1，a(2)-a(k+2)=(x2-y2)*m2,,这个时候求一个m，不就是求两式的最大公因数吗，为什么是最大公因数，因为题中m有限制m要求大于等于2，它们的公因数可能有很多个，但是大于2的不一定有，所以求一个最大公因数，看看是否大于2。那么解法显而易见了，枚举k，然后求每个子数组对应元素差的最大公因数，看它是否大于等于2，及不等于1，如果是ans++。

using i64 = long long;
i64 gcd(i64 a, i64 b) {while (b) {i64 temp = b;b=a%b;a = temp;}return std::abs(a);
}
void solve() {int n;std::cin >> n;std::vector<int> a(n);for (int i = 0; i < n; i++) {std::cin >> a[i];}int ans = 0;for (int k = 1; k <= n; k++) {if (n % k == 0) {int g = 0;for (int i = k; i < n; i++) {g = gcd(g, a[i] - a[i - k]);}ans += (g != 1);}}std::cout << ans << "\n";
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t;std::cin >> t;while (t--) {solve();}return 0;
}