首先可以把 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
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing 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