BZOJ 2694 & 4659 Lcm February 28, 2017 ###Description ![fa(1).jpg][1] ###Solution $$\sum_i^n\sum_j^m[\mu(gcd(i,j))\neq 0]lcm(i,j)$$ $$=\sum_k^n|\mu(k)|\sum_i^{\frac{n}{k}}\sum_j^{\frac{n}{k}}[gcd(i,j)=1]i\cdot j\cdot k$$ $$=\sum_k^n|\mu(k)|\cdot k\sum_d^{\frac{n}{k}}\mu(d)\cdot d^2\sum_i^{\frac{n}{k\cdot d}}\sum_j^{\frac{m}{k\cdot d}}i\cdot j$$ $$=\sum_k^n\sum_d[d|k]\mu(d)\cdot d^2\cdot|\mu(\frac{k}{d})|\cdot\frac{p}{d}\cdot\frac{\frac{n}{k}\cdot(\frac{n}{k}+1)}{2}\cdot\frac{\frac{m}{k}\cdot(\frac{m}{k}+1)}{2}$$ 最后的式子，前面是积性函数，后面根号分块 ###Code ```c++ #define _GLIBCXX_IOSTREAM #include<bits/stdc++.h> #define N 4000001 int pri[N],pm,f[N],ps[N],pc[N]; bool np[N]; int main() { for(int i=2;i<N;i++) { if(!np[i])pri[pm++]=i,f[i]=1,ps[i]=i,pc[i]=1; int rf; if(pc[i]==1)rf=f[i]*(ps[i]-ps[i]*ps[i]); else if(pc[i]==2)rf=-f[i]*ps[i]*ps[i]*ps[i]; else rf=0; for(int j=0;i*pri[j]<N;j++) { np[i*pri[j]]=1; if(i%pri[j])f[i*pri[j]]=rf,ps[i*pri[j]]=pri[j],pc[i*pri[j]]=1; else { f[i*pri[j]]=f[i],ps[i*pri[j]]=pri[j],pc[i*pri[j]]=pc[i]+1; break; } } f[i]=rf; } f[1]=1; for(int i=1;i<N;i++) f[i]+=f[i-1]; int T; for(scanf("%d",&T);T--;) { int n,m,ans=0; scanf("%d%d",&n,&m); for(int i=1,t,p,q;i<=n&&i<=m;i=t+1) { p=n/i,q=m/i,t=std::min(n/p,m/q); ans+=(f[t]-f[i-1])*p*(p+1)*q*(q+1)>>2; } printf("%d\n",ans&0x3fffffff); } } ``` [1]: /usr/uploads/2017/02/3245901942.jpg [2]: /usr/uploads/2017/02/1279320617.png