首先可以把 i mod n=j mod n的看成是同一类，i mod s=j mod s的也看成是同一类，也就是i mod gcd(s,n)的是同一类，很好理解，但是不会数学证明...大概可以想成数轴上一点可以向左向右跳s或n，根据错位相消能互达的两点最小距离为gcd(s,n)，所以如果选择点i必须满足a(i)>=a(i+k*gcd(s, n))。
于是可以枚举d表示gcd(s, n)，处理出所有可以被选择的点，1表示可选，0表示不可选，组成一个01序列，倍增一次后求出f[i]表示每一个点出发最长的连续的1，再预处理出cnt[i]表示1~i中gcd(i, n)==d的个数，最后枚举起点，sigma(cnt[f[i]])即为这个gcd(s, n)的贡献。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #define ll long long using namespace std; const int maxn=500010, inf=1e9+1; int n; int a[maxn], g[maxn], mx[maxn], can[maxn], f[maxn], cnt[maxn]; ll ans; void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline int gcd(int a, int b){return b?gcd(b, a%b):a;} int main() { read(n); for(int i=0;i<n;i++) read(a[i]); for(int i=1;i<=n;i++) g[i]=gcd(i, n); for(int d=1;d<=n;d++) if(!(n%d)) { for(int i=0;i<d;i++) mx[i]=0; for(int i=0;i<n;i++) mx[i%d]=max(mx[i%d], a[i]); for(int i=0;i<n;i++) can[i]=can[i+n]=(a[i]==mx[i%d]); for(int i=(n<<1)-2;~i;i--) f[i]=min(n-1, (can[i]?f[i+1]+1:0)); for(int i=1;i<=n;i++) cnt[i]=cnt[i-1]+(g[i]==d); for(int i=0;i<n;i++) ans+=cnt[f[i]]; } printf("%lld ", ans); }