C. Partitioning the Array

原题：Problem - C - Codeforces

官方题解：Editorial for Codeforces Round #919 (Div. 2) - Codeforces

收获及反思：

同余推理，如：

判断x,y两数是否可能同余，并找出模数m.

设相同的余数为k, x=a*m+k, y=b*m+k

两式相减，x-y=(a-b)m,

可见，若要x,y同余，则应使m能整除 x-y.

#include<bits/stdc++.h> using namespace std; int main(){ int t;cin>>t; while(t--){ int n;cin>>n; vector<int> a(n+1); for(int i=1;i<=n;i++) cin>>a[i]; int ans=0; for(int k=1;k<=n;k++){ if(n%k==0){ int g=0; for(int i=1;i<=n/k;i++){ for(int j=n/k;i+j<=n;j+=n/k){ g=__gcd(g,abs(a[i+j]-a[i+j-n/k])); } } if(g!=1) ans++; } } cout<<ans<<endl; } }