因为区间 gcd 的变换不会超过 log 个,所以我们可以暴力枚举区间起点,复杂度是 n*logn 的
#include <bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<=b;++i) #define fd(i,a,b) for(int i=a;i>=b;--i) ,mod=; template <typename T> bool check_Max(T &x, const T&y) {return x<y?x=y,false:true;} template <typename T> bool check_Min(T &x, const T&y) {return x>y?x=y,false:true;} inline int gi() { ; char o; bool f=true; for(;!isdigit(o=getchar());) if(o=='-') f=false; )+(x<<)+(o&); ; } template <typename T> inline void Md(T &x) {if(x>=mod) x-=mod;} int gcd(int x,int y) { return x?gcd(y%x,x):y;} int gd1[maxn],gd2[maxn],nt[maxn],a[maxn],n,ans; int main() { #ifndef ONLINE_JUDGE freopen("10.in","r",stdin); #endif n=gi(); rep(i,,n) gd1[i]=gd2[i]=a[i]=gi(); rep(i,,n) gd1[i]=gcd(gd1[i-],gd1[i]); fd(i,n-,) gd2[i]=gcd(gd2[i+],gd2[i]); rep(i,,n) nt[i]=gd2[i]==gd2[i-]?nt[i-]:i-; rep(i,,n) { ]; ) Md(ans+=pos%mod); int L=n; while(L>i) { ,nt[L]+); pos=gcd(pos,gd2[R]); // printf("i=%d L=%d R=%d pos=%d--\n",i,L,R,pos);//de bug Md(ans+=1LL*pos*(L-R+)%mod); L=R-; } } ,R,pos=gd2[L]; ) { R=max(,nt[L]+),pos=gd2[R]; // peintf("L=%d R=%d pos=%d\n",L,R,pos); //de bug Md(ans+=1LL*pos*(L-R+)%mod); L=R-; } printf("%d\n",ans); ; }
今天的水题计划就到这里了,顺带提一句,今天S8世界总决赛 小组赛IG vs GRX时Stitch 的反向Q,连皮肤都和当年韦神的一样
放个图感受一下