返回首页 返回专题

【BZOJ2820】YY的GCD 题解

先来画柿子！

注意F(T)表达式中的p是一个质数。接下来我们考虑怎么求出F数组

如果给一个μ≠0的数乘上一个它已有的质因数p，设乘上之后的数为T，那么会发现，F(T)的各项中，只有μ(T/p)≠0，因为枚举其它质因数q时，T/q都会包含两个相同的质因数p，导致μ=0。于是得到第一个结论：若p∣x，其中p是质数，那么F(px)=F(x)

设一个数为x，乘上的它还没有的质因数p后为T，那么枚举除p之外的质因子q，不难想到T/q与x/q相比，都多了一个质因数p，于是μ的符号全部取反，而p这个质因子对T的贡献就是μ(T/p)，即μ(x)。于是又得到一个结论：若p mod x≠0，其中p是质数，那么F(px)=μ(x)-F(x)

有了这两个结论，就可以线性筛处理出F数组了！然后求一个前缀和就可以了！

时间复杂度O(n+T sqrt(n))

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=10000000;
int u[N+10],f[N+10],sum[N+10];
int prime[N+10],tot=0;
bool mark[N+10];

void Init()
{
	memset(mark,0,sizeof(mark));
	u[1]=1;f[1]=0;
	for(int i=2;i<=N;i++)
	{
		if(!mark[i])
		{
			prime[++tot]=i;
			u[i]=-1;f[i]=1;
		}
		for(int j=1;j<=tot&&i*prime[j]<=N;j++)
		{
			mark[i*prime[j]]=1;
			if(i%prime[j]) u[i*prime[j]]=-u[i],f[i*prime[j]]=u[i]-f[i];
			else {u[i*prime[j]]=0,f[i*prime[j]]=u[i];break;}
		}
	}
	sum[0]=0;
	for(int i=1;i<=N;i++) sum[i]=sum[i-1]+f[i];
}

int main()
{
	Init();
	int T,n,m,j;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&m);
		if(n>m) swap(n,m);
		LL ans=0;
		for(int k=1;k<=n;k=j+1)
		{
			j=min(n/(n/k),m/(m/k));
			ans+=(LL)(sum[j]-sum[k-1])*(n/k)*(m/k);
		}
		printf("%lld\n",ans);
	}
	return 0;
}