莫比乌斯反演套路三、四--BZOJ2154: Crash的数字表格 && BZOJ2693: jzptab
t<=1e4个询问每次问n,m<=1e7,$\sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m}lcm(x,y)$。
首先题目要求的是$\sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m}lcm(x,y)=\sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m}\frac{x*y}{(x,y)}$,
啊很好那来枚举gcd吧,$\sum_{t=1}^{min(n,m)} t^{-1} f(t)$,其中$f(t)=\sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m,(x,y)=t} x*y$,哦太棒了来反演吧。
套路三:反演个鬼啊先化一化:$f(t)=t*t*\sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m,(x,y)=1} x*y$。
好来演$g(t)=\sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m}xy=\frac{x*(x+1)}{2}\frac{y*(y+1)}{2}$,$f(t)=t*t*\sum_{1\leqslant d\leqslant t}\mu(d)\frac{n}{d}\frac{m}{d}$。
代进去!前后枚举约数和除数暴力算即可。$\sqrt n * \sqrt n$=O(n)搞定。
套路三就是反演之前冷静一下变个型啦。
套路四:化个鬼啊直接反演:$\sum_{t=1}^{min(n,m)} t^{-1} \sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m,(x,y)=t} x*y =\sum_{t=1}^{min(n,m)} t^{-1} \sum_{t|d} \mu(\frac{d}{t}) \sum_{1\leqslant x\leqslant n,1\leqslant y\leqslant m,d|(x,y)} x*y=\sum_{t=1}^{min(n,m)} t^{-1} \sum_{t|d} \mu(\frac{d}{t}) * d^2 * \frac{(1+\frac{n}{d})\frac{n}{d}}{2} \frac{(1+\frac{m}{d})\frac{m}{d}}{2}=\sum_{t=1}^{min(n,m)}\sum_{t|d} \mu(\frac{d}{t})* \frac{d}{t} * d *\frac{(1+\frac{n}{d})\frac{n}{d}}{2} \frac{(1+\frac{m}{d})\frac{m}{d}}{2} = \sum_{d=1}^{min(n,m)}\frac{(1+\frac{n}{d})\frac{n}{d}}{2} \frac{(1+\frac{m}{d})\frac{m}{d}}{2} * d * \sum_{t|d} \mu(t) * t$。
漂亮!前面一坨可以根号枚举,如果能得到线性得到所有$d * \sum_{t|d} \mu(t) * t$就可以了。先不*d,这东西不是个积性函数么?(打表可知,易证)
线性筛筛出来然后记个前缀和,就可以$O(n)$预处理,然后$O(\sqrt n)$回答每个询问了。
1 //#include<iostream> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cstdio> 5 //#include<bitset> 6 #include<algorithm> 7 //#include<cmath> 8 using namespace std; 9 10 const int mod=20101009; 11 int T,n,m; 12 #define maxn 10000011 13 int inv[maxn],miu[maxn],prime[maxn],sum[maxn],lp; bool notprime[maxn]; 14 void pre(int n) 15 { 16 miu[1]=1; lp=0; sum[1]=1; 17 long long tmp; 18 for (int i=2;i<=n;i++) 19 { 20 if (!notprime[i]) {prime[++lp]=i; miu[i]=-1; sum[i]=mod-i+1;} 21 for (int j=1;j<=lp && (tmp=1ll*prime[j]*i)<=n;j++) 22 { 23 notprime[tmp]=1; 24 if (i%prime[j]) miu[tmp]=-miu[i],sum[tmp]=1ll*sum[i]*sum[prime[j]]%mod; 25 else {miu[tmp]=0; sum[tmp]=sum[i]; break;} 26 } 27 } 28 for (int i=2;i<=n;i++) sum[i]=1ll*sum[i]*i%mod,sum[i]+=sum[i-1],sum[i]-=sum[i]>=mod?mod:0; 29 // for (int i=1;i<=n;i++) cout<<sum[i]<<' ';cout<<endl; 30 } 31 32 int main() 33 { 34 scanf("%d%d",&n,&m); 35 pre(min(n,m)); 36 // scanf("%d",&T); 37 //while (T--) 38 //{ 39 int ans=0; 40 for (int i=1,to=min(n,m),last,hh=((mod+1)>>1)*1ll*((mod+1)>>1)%mod;i<=to;i=last+1) 41 { 42 last=min(n/(n/i),m/(m/i)); 43 ans+=1ll*(n/i)*(m/i)%mod*(1+(n/i))%mod*(1+(m/i))%mod*hh%mod*(sum[last]-sum[i-1])%mod; 44 ans-=ans>=mod?mod:0,ans+=ans<0?mod:0; 45 } 46 printf("%d\n",ans); 47 //} 48 return 0; 49 }View Code