51nod1222 最小公倍数计数 【莫比乌斯反演】

题目描述

f(n)=(lcm(x,y)==n的二元组(x<=y)的数量)
求∑i=ab​f(i)
1≤a≤b≤1011

题目分析

实质上就是求i∑​j∑​lcm(i,j)≤n的数量，最后加上n，再除以2
看到这种条件里面带不等式的，求和符号能省去范围的就省掉，不然会很冗杂
枚举gcd:
=d=1∑n​i∑​j∑​[(i,j)==1][ijd<=n]
反演，去掉[(i,j)==1]:
=k=1∑n​​μ(k)d∑​i∑​j∑​[ijd<=⌊k2n​⌋]
那么现在就是求g(n)=∑a​∑b​∑c​[abc<=n]

假设a<=b<=c，那么只需要枚举不超过n31​的a，再枚举不超过an​​的b，统计c的个数，在配上对应的容斥系数，考虑一下两个数，三个数相等的情况即可。
求g(n)的时间复杂度为∑i=1n31​​(in​​−i)，O(n32​)

• PS:
  枚举lcm，原式=i=1∑n​x∣i∑​y∣i∑​[(x,y)==1]=i=1∑n​σ0​(i2)
  问题等同于Counting Divisors

#include<cstdio>
#define LL long long
const int N = 10000005;
int p[N/10],mu[N+5];
bool v[N+5];
void Prime()
{
	mu[1]=1;int cnt=0;
	for(int i=2;i<=N;i++)
	{
		if(!v[i]) p[++cnt]=i,mu[i]=-1;
		for(int j=1,k;j<=cnt&&p[j]*i<=N;j++)
		{
			v[k=p[j]*i]=1;
			if(i%p[j]==0) {mu[k]=0;break;}
			mu[k]=-mu[i];
		}
	}
}
LL solve(LL n)
{
	LL ans=0;
	for(LL k=1;k*k<=n;k++) if(mu[k])
	{
		LL m = n/(k*k), ret=0;
		for(LL i=1;i*i*i<=m;i++)
		{
			for(LL j=i+1;i*j*j<=m;j++) ret+=(m/(i*j)-j)*6+3;
			ret+=(m/(i*i)-i)*3+1;
		}
		ans+=mu[k]*ret;
	}
	return (ans+n)/2;
}
int main()
{
	Prime();
	LL a,b;
	scanf(\"%lld%lld\",&a,&b);
	printf(\"%lld\",solve(b)-solve(a-1));
}