C. Partitioning the Array - 思维 + gcd

发布时间:2024年01月14日

题面

分析

如果让两个数满足对某一个数取模后相等,那么也就是 x m o d m = y m o d m x mod m = y mod m xmodm=ymodm,那么也就是 ( x ? y ) m o d m = = 0 m o d m (x - y) mod m == 0 mod m (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();
    }
}
文章来源:https://blog.csdn.net/m0_75129175/article/details/135589634
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。