Codeforces 582C. Superior Periodic Subarrays（数学+计数）

　　首先可以把 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=, inf=1e9+;

int n;

int a[maxn], g[maxn], mx[maxn], can[maxn], f[maxn], cnt[maxn];

ll ans;

void read(int &k)

{

    int f=; k=; char c=getchar();

    while(c<'' || c>'') c=='-' && (f=-), c=getchar();

    while(c<='' && c>='') k=k*+c-'', 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=;i<n;i++) read(a[i]);

    for(int i=;i<=n;i++) g[i]=gcd(i, n);

    for(int d=;d<=n;d++)

    if(!(n%d))

    {

        for(int i=;i<d;i++) mx[i]=;

        for(int i=;i<n;i++) mx[i%d]=max(mx[i%d], a[i]);

        for(int i=;i<n;i++) can[i]=can[i+n]=(a[i]==mx[i%d]);

        for(int i=(n<<)-;~i;i--) f[i]=min(n-, (can[i]?f[i+]+:));

        for(int i=;i<=n;i++) cnt[i]=cnt[i-]+(g[i]==d);

        for(int i=;i<n;i++) ans+=cnt[f[i]];

    }

    printf("%lld\n", ans);

}