C. Partitioning the Array - 思维 + gcd

题面

分析

如果让两个数满足对某一个数取模后相等，那么也就是$xmodm=ymodm$，那么也就是$(x?y)modm==0modm$，因此可以推出，对于每一个子数组的相同位置都要满足二者绝对值之差对某一个数取模能够等于0，那么也就是众多绝对值之差的最大公约数，如果最大公约数存在，那么也就存在一个符合的答案。

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5 + 10;

int a[N];

int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}

void solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    ll ans = 0;
    vector<int> x;
    for(int i = 1; i <= n / i; i ++) {
        if(n % i == 0) {
            x.push_back(i);
            if(i != n / i) x.push_back(n / i);
        }
    }
    for(auto j: x) {
        int sum = 0;
        for(int i = 1; i + j <= n; i ++) sum = gcd(sum, abs(a[i] - a[i + j]));
        if(sum != 1) ans ++;
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while(T --) {
        solve();
    }
}