1098E - Fedya the Potter - CodeForces Solution

#include<bits/stdc++.h>
#define For(a,b,c) for(int a=b;a<=c;++a)
#define Dor(a,b,c) for(int a=b;a>=c;--a)
using namespace std;
typedef long long LL;
enum{N=50007,M=N<<1};
int n,m,lg,G[18][N];
LL w,s,t,k,C[M],SC[M],S[M];
struct O {
LL u,r,s;
O operator * (const O &_) const {
return (O){u+_.u,r+_.r,s+_.s+u*_.r};
}
}E=(O){0,0,0},U=(O){1,0,0},R=(O){0,1,0};
O operator ^ (O x,int k) {
O r=E;
while(k) {
if(k&1) r=r*x;
x=x*x,k>>=1;
}
return r;
}
O god(LL n,LL a,LL b,LL c,O U,O R) {
if(!n) return E;
if(a>=c) return god(n,a%c,b,c,U,(U^(a/c))*R);
LL t=(a*n+b)/c;
if(!t) return R^n;
return (R^((c-b-1)/a))*U*god(t-1,c,(c-b-1)%a,a,R,U)*(R^(n-(c*t-b-1)/a));
}
int gcd(int a,int b) {
return b?gcd(b,a%b):a;
}
void add(int i,int j) {
if(!j||i==j) return;
LL ca=C[i],cb=C[j],n=k-(S[i-1]-S[j])-(ca+1)*i;
LL l=max(1LL,(j-n+i-1)/i),r=min(ca,(cb*j-n)/i);
t+=(ca-r)*cb;
if(t>=w) return;
if(l<=r) {
n+=l*i;
LL f=((U^(n/j))*R*god(r-l,i,n%j,j,U,R)).s;
t+=f;
}
}
bool ok() {
int j=1; s=t=0;
For(i,1,m) {
s+=C[i]*i;
add(i,j-1);
if(t>=w) return 1;
while(s>k) {
s-=C[j]*j;
add(i,j);
if(t>=w) return 1;
++j;
}
if(j>i) {
LL c=k/i,n=C[i];
t+=(n+n-c+1)*c/2;
if(t>=w) return 1;
continue;
}
t+=(SC[i-1]-SC[j-1])*C[i]+C[i]*(C[i]+1)/2;
if(t>=w) return 1;
}
return 0;
}
int main() {
scanf("%d",&n),lg=log2(n);
For(i,1,n) scanf("%d",&G[0][i]),m=max(m,G[0][i]);
For(i,1,lg)
For(j,1,n-(1<<i)+1) G[i][j]=gcd(G[i-1][j],G[i-1][j+(1<<i>>1)]);
For(i,1,n) {
int u=i,p=i,g=G[0][i];
while(u<=n) {
Dor(i,lg,0) if(G[i][u]&&G[i][u]%g==0) u+=1<<i;
C[g]+=u-p,p=u,g=gcd(g,G[0][u]);
}
}
LL l=1,r=0,c=1LL*n*(n+1)/2; w=c*(c+1)/2,w=(w+1)/2;
For(i,1,m) r+=C[i]*i,SC[i]=SC[i-1]+C[i],S[i]=S[i-1]+C[i]*i;
while(l<=r) {
LL m=(l+r)>>1;
if(k=m,ok()) r=m-1;
else l=m+1;
}
printf("%lld",l);
return 0;
}