bzoj2693:jzptab(莫比乌斯反演)

Author Avatar
Sakits 4月 08, 2018

题解

ans=i=1nj=1md=1n[(i,j)=d]d1×i×j=d=1ni=1ndj=1md[(i,j)=1]×d×i×j=d=1ni=1ndj=1mdk(i,j)μ(k)×d×i×j=d=1ndi=1ndij=1mdjk(i,j)μ(k)=d=1ndk=1ndk2μ(k)i=1ndkij=1mdkj=T=1nTkTkμ(k)i=1nTij=1mTj\begin{aligned} ans&=\sum_{i=1}^n\sum_{j=1}^m\sum_{d=1}^n[(i,j)=d]*d^{-1}\times i\times j\\ &=\sum_{d=1}^n\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}[(i,j)=1]\times d\times i\times j\\ &=\sum_{d=1}^n\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}\sum_{k|(i,j)}\mu(k)\times d\times i\times j\\ &=\sum_{d=1}^nd\sum_{i=1}^{\left \lfloor \frac{n}{d} \right \rfloor}i\sum_{j=1}^{\left \lfloor \frac{m}{d} \right \rfloor}j\sum_{k|(i,j)}\mu(k)\\ &=\sum_{d=1}^nd\sum_{k=1}^{\left \lfloor \frac{n}{d} \right \rfloor}k^2\mu(k)\sum_{i=1}^{\left \lfloor \frac{n}{dk} \right \rfloor} i\sum_{j=1}^{\left \lfloor \frac{m}{dk} \right \rfloor}j\\ &=\sum_{T=1}^nT\sum_{k|T}k\mu(k)\sum_{i=1}^{\left \lfloor \frac{n}{T} \right \rfloor} i\sum_{j=1}^{\left \lfloor \frac{m}{T} \right \rfloor}j\\ \end{aligned}

  预处理kTkμ(k)\sum_{k|T}k\mu(k)即可,这是个积性函数的点积的狄利克雷卷积,所以同样是个积性函数,线性筛即可。
  imodprimej=0i\mod prime_j=0的时候直接取ii的值即可,因为μ(i×primej)=0\mu(i\times prime_j)=0

代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
#define MOD(x) ((x)>=mod?(x)-mod:(x))
using namespace std;
const int maxn=10000010, inf=1e9, mod=1e8+9;
int n, m, cntp, ans, T;
int sum[maxn], pri[maxn], mu[maxn], tmu[maxn];
bool v[maxn];
inline void read(int &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}
inline void getmu(int n)
{
	tmu[1]=1;
	for(int i=2;i<=n;i++) 
	{
		if(!v[i]) pri[++cntp]=i, tmu[i]=MOD(-i+1+mod);
		for(int j=1;1ll*pri[j]*i<=n;j++)
		{
			v[pri[j]*i]=1;
			if(i%pri[j]==0)
			{
				tmu[pri[j]*i]=tmu[i];
				break;
			} 
			tmu[pri[j]*i]=1ll*tmu[i]*tmu[pri[j]]%mod;
		}
	}
	for(int i=1;i<=n;i++) sum[i]=(sum[i-1]+1ll*i*tmu[i])%mod;
}
int main()
{
	read(T); getmu(10000000);
	while(T--)
	{
		ans=0;
		read(n); read(m); if(n>m) swap(n, m);
		for(int i=1, last;i<=n;i=last+1)
		{
			last=min(n/(n/i), m/(m/i));
			int SUM1=MOD(sum[last]-sum[i-1]+mod);
			int SUM2=(1ll*(1+(n/i))*(n/i)>>1)%mod;
			int SUM3=(1ll*(1+(m/i))*(m/i)>>1)%mod;
			ans=(ans+1ll*SUM1*SUM2%mod*SUM3)%mod;
		}
		printf("%d\n", ans);
	}
}