莫比乌斯反演套路三、四--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)$回答每个询问了。

 //#include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<cstdio>

 //#include<bitset>

 #include<algorithm>

 //#include<cmath>

 using namespace std;

 const int mod=;

 int T,n,m;

 #define maxn 10000011

 int inv[maxn],miu[maxn],prime[maxn],sum[maxn],lp; bool notprime[maxn];

 void pre(int n)

 {

     miu[]=; lp=; sum[]=;

     long long tmp;

     for (int i=;i<=n;i++)

     {

         if (!notprime[i]) {prime[++lp]=i; miu[i]=-; sum[i]=mod-i+;}

         for (int j=;j<=lp && (tmp=1ll*prime[j]*i)<=n;j++)

         {

             notprime[tmp]=;

             if (i%prime[j]) miu[tmp]=-miu[i],sum[tmp]=1ll*sum[i]*sum[prime[j]]%mod;

             else {miu[tmp]=; sum[tmp]=sum[i]; break;}

         }

     }

     for (int i=;i<=n;i++) sum[i]=1ll*sum[i]*i%mod,sum[i]+=sum[i-],sum[i]-=sum[i]>=mod?mod:;

 //    for (int i=1;i<=n;i++) cout<<sum[i]<<' ';cout<<endl;

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     pre(min(n,m));

 //    scanf("%d",&T);

 //while (T--)

 //{

     int ans=;

     for (int i=,to=min(n,m),last,hh=((mod+)>>)*1ll*((mod+)>>)%mod;i<=to;i=last+)

     {

         last=min(n/(n/i),m/(m/i));

         ans+=1ll*(n/i)*(m/i)%mod*(+(n/i))%mod*(+(m/i))%mod*hh%mod*(sum[last]-sum[i-])%mod;

         ans-=ans>=mod?mod:,ans+=ans<?mod:;

     }

     printf("%d\n",ans);

 //}

     return ;

 }

巴特西

莫比乌斯反演套路三、四--BZOJ2154: Crash的数字表格 && BZOJ2693: jzptab

最新文章

热门文章