[JSOI2015]最大公约数

链接:https://www.luogu.com.cn/problem/P5502 题目描述：对于一个序列$a$，求$\sum_{i=l}^{r}gcd(a_{l},....,a_r)\times (r-l+1)$的最大值。 题解：利用"签到游戏"的知识，我们可以知道这样的$gcd$只有$nlogn$个,所以对于每一个$l$，我们可以在前一个段点$r'$的基础上，在[$r',n$]二分一个最小的满足$gcd(a_{l},....,a_r)!=gcd(a_{l},....,a_r')$的$r$，这样直接做是$O(nlog_{3}n\times gcd)$的，考虑优化。 我们可以线段树二分，这样复杂度降至$O(nlog_{2}n\times gcd)$了。 ``` #include #include using namespace std; struct node { long long l,r,data; }; long long a[2000001],n; node tree[2000001]; long long gcd(long long a,long long b) { if (b==0) return a; return gcd(b,a%b); } void build(int k,int l,int r) { tree[k].l=l; tree[k].r=r; int mid=(l+r)/2; if (l==r) { tree[k].data=a[l]; return; } build(k*2,l,mid); build(k*2+1,mid+1,r); tree[k].data=gcd(tree[k*2].data,tree[k*2+1].data); return; } long long query(int k,int l,int r) { if (tree[k].l==l&&tree[k].r==r) return tree[k].data; int mid=(tree[k].l+tree[k].r)/2; if (l<=mid&&r<=mid) return query(k*2,l,r); if (l>=mid+1&&r>=mid+1) return query(k*2+1,l,r); return gcd(query(k*2,l,mid),query(k*2+1,mid+1,r)); } void add(int k,int x) { if (tree[k].l==tree[k].r) { tree[k].data=0; return; } int mid=(tree[k].l+tree[k].r)/2; if (x<=mid) { add(k*2,x); tree[k].data=gcd(tree[k*2].data,tree[k*2+1].data); return; } else { add(k*2+1,x); tree[k].data=gcd(tree[k*2].data,tree[k*2+1].data); return; } return; } int segment_search(int k,int l,long long x,long long d) { if (tree[k].l==tree[k].r) return tree[k].l; int mid=(tree[k].l+tree[k].r)/2; if (gcd(d,tree[k*2].data)<x&&l<=mid) return="" segment_search(k*2,l,x,d);="" else="" if="" (gcd(d,tree[k].data)<x)="" segment_search(k*2+1,l,x,gcd(d,tree[k*2].data));="" n+1;="" }="" int="" main()="" {="" long="" last,res,ans="0;" cin="">>n; for (int i=1;i<=n;++i) cin>>a[i]; build(1,1,n); for (int i=1;i<=n;++i) { res=a[i]; last=0; for (int j=i;j<=n;j=last+1) { last=segment_search(1,i,res,0)-1; ans=max(ans,(last-i+1)*res); if (last!=n) res=query(1,i,last+1); } add(1,i); } cout<