2019华工校赛H .Parco_Love_GCD

https://ac.nowcoder.com/acm/contest/625/H
题意：有一个长度为 $n(5\ast 10^5)$n(5∗105)的数组，求所有子区间的gcd之和对 $1e9+7$1e9+7取模的结果。
思路：设 $A=a_1^{p1}\ast a_2^{p2}\ast a_3^{p3},B=a_1^{q1}\ast a_2^{q2}\ast a_3^{q3},$A=a1p1​∗a2p2​∗a3p3​,B=a1q1​∗a2q2​∗a3q3​,
$那么gcd(A,B)=a_1^{min\{p1,q1\}}\ast a_2^{min\{p2,q2\}}\ast a_3^{\{p3,q3\}}$那么gcd(A,B)=a1min{p1,q1}​∗a2min{p2,q2}​∗a3{p3,q3}​
根据这个性质，求所有区间的 $gcd$gcd可以转化为 $RMQ$RMQ问题， $O\left(nlog\right(n\left)\right)预处理,O\left(1\right)查询$O(nlog(n))预处理,O(1)查询
然后这道题可以转化为：以每一个位置作为区间左端点，右端点一直向右移，构成的所有区间gcd之和。
因为固定左端点，右端点向右移的过程中， $gcd$gcd是单调递减的，可以二分处理。为什么要二分呢？因为移动右端点的过程中，有很多相邻的点作为右端点时 $gcd$gcd是相同的。如果右边很多互素的，不久之后 $gcd$gcd全部是1；如果有很多相等的元素， $gcd$gcd相等直接 $log复杂度$log复杂度跳过去；如果右边以幂次排列，因为最大元素在int内，最多按2的幂次跳30次。
综上，这个方法的时间复杂度大约是 $O\left(nlog\right(n\left)\right)。$O(nlog(n))。
这个二分的写法还是要考虑清楚怎么写再去写的。

#include<bits/stdc++.h>
using namespace std;
#define maxn 500000+100
#define mod 1000000007

int n,a[maxn];
int st[30][maxn];
long long ans;

int query(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=r-l+1)k++;
    return __gcd(st[k][l],st[k][r-(1<<k)+1]);
}

void debug()
{
    for(int i=0;i<3;i++)for(int j=1;j<=n;j++)
        printf("%d,%d:%d\n",i,j,st[i][j]);
}

int main()
{
    //freopen("input.in","r",stdin);
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)st[0][i]=a[i];
    for(int i=1;(1<<i)<=n;i++)
        for(int j=1;j+(1<<i)-1<=n;j++)st[i][j]=__gcd(st[i-1][j],st[i-1][j+(1<<(i-1))]);  
    for(int i=1;i<=n;i++)		//枚举左端点
    {
        int g=a[i];
        int start=i;
        while(start<=n)		//[start,last]满足gcd(i...start)=gcd(i...start+1)=gcd(i...last)
        {
        	int l=start,r=n,last;	//l和r是为了以start为起点找到last
            while(l<=r)
            {
                int m=(l+r)/2;
                if(query(i,m)==g)last=m,l=m+1;
                else r=m-1;
            }
            ans=(ans+(long long)g*(last-start+1))%mod;
            g=query(i,last+1);
            start=last+1;
        }
    }
    cout<<ans<<endl;
    return 0;
}