【题目】

【题意】给定循环节长度为n的无限循环数列，定义(l,s)表示起点为l的长度为s的子串，(l,s)合法要求将子串从该起点开始以s为循环节长度无限循环中每个数字都>=数列中对应位置的数字，求合法(l,s)的数量。0<=l<n，1<=s<=n，n<=2*10^5，1<=ai<=10^6。

【算法】数论，计数问题

【题解】先不考虑起点，对于选定的s，子串中的数字必须≥所有间隔为g=gcd(s,n)的数字（核心思想）。

例如在1 2 3 4 5 6，g=2时，1 3 5为一组，2 4 6为一组，子串中如果包含某一组的一个，那个就必须≥整组的数字。

枚举g，对于数列中g个[数字间隔为g的序列]，显然每个序列中只有最大的数字才有可能被选择为子串，那么处理后我们得到了01数列。

对于01数列，我们要用连续的1凑出长度s满足gcd(s,n)=g，先使用双指针统计出几段连续的1，对于每一段连续的1枚举长度贡献答案。

复杂度O(d(n)*n)，其中d(n)为n的因子个数。

 

以上为CF官方题解，在处理01序列的时候可以采用一种较简单的写法：

枚举g，预处理c[x]表示长度i=1~x中满足g=gcd(i,n)的 i 的个数。

处理出01序列，然后将链复制一遍，倒着计算出b[i]表示从i出发最长的连续1个数。

最后枚举起点l，每个点贡献答案c[b[i]]。

#include
      
       #include
       
        using namespace std;const int maxn=200010;int n,a[maxn],b[maxn<<1],c[maxn],mx[maxn],gc[maxn];int gcd(int a,int b){
    return !b?a:gcd(b,a%b);}//learn from LIBERATORint main(){    scanf("%d",&n);    for(int i=0;i
        
         =0;i--)if(b[i])b[i]+=b[i+1];        for(int i=0;i