∑i=LR∑j=LRgcd(ai,aj)=∑i=LR∑j=LR∑d|ai,d|ajϕ(d)=∑dϕ(d)(∑i=LR[d|ai])2
这个东西现在想不到什么好的方法维护 就暴力跑莫队吧
#include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<vector> #include<cstring> #define cl(x) memset(x,0,sizeof(x)) using namespace std; typedef long long ll; inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; } return *p1++; } inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b; } const int N=20005; int phi[N]; vector<int> fac[N]; inline void Pre(int n=20000){ phi[1]=1; int i,j; for (int i=1;i<=n;i++) if(!phi[i]) for (j=i;j<n;j+=i){ if (!phi[j]) phi[j]=j; phi[j]-=phi[j]/i; } for (int i=1;i<=n;i++) for (int j=i;j<=n;j+=i) fac[j].push_back(i); } int n,a[N]; int pos[N]; struct event{ int l,r,idx; bool operator < (const event &B)const{ return pos[l]==pos[B.l]?r<B.r:pos[l]<pos[B.l]; } }eve[N]; int tot;ll ans[N]; int num[N]; ll cur; inline void add(int t){ for (int i=0;i<(int)fac[t].size();i++){ int x=fac[t][i]; cur+=(ll)num[x]*phi[x]; num[x]++; } } inline void del(int t){ for (int i=0;i<(int)fac[t].size();i++){ int x=fac[t][i]; num[x]--; cur-=(ll)num[x]*phi[x]; } } int main(){ int T,Case=0; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(T); Pre(); while (T--){ printf("Case #%d:\n",++Case); read(n); for (int i=1;i<=n;i++) read(a[i]); read(tot); for (int i=1;i<=tot;i++) read(eve[i].l),read(eve[i].r),eve[i].idx=i; int B=sqrt((double)n)+1; for (int i=1;i<=n;i++) pos[i]=(i-1)/B+1; sort(eve+1,eve+tot+1); int l=1,r=0; for (int i=1;i<=tot;i++){ while (r<eve[i].r) add(a[++r]); while (r>eve[i].r) del(a[r--]); while (l<eve[i].l) del(a[l++]); while (l>eve[i].l) add(a[--l]); ans[eve[i].idx]=cur; } for (int i=1;i<=tot;i++) printf("%I64d\n",ans[i]); cl(num); cur=0; } return 0; }