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

参考：https://www.cnblogs.com/SilverNebula/p/7045199.html

所是反演其实反演作用不大，又是一道做起来感觉诡异的题

转成前缀和相减的形式

\[\sum_{i=1}^{n}\sum_{j=1}^{n}[\frac{i*j}{gcd(i,j)}\leq n]
\]

\[\sum_{d=1}^{n}\sum_{i=1}^{\left \lfloor \frac{n}{d}\right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{d}\right \rfloor}[gcd(i,j)==1][i*j\leq\left \lfloor \frac{n}{d} \right \rfloor]
\]

\[\sum_{k=1}^{n}
\mu(k)\sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor}\sum_{i=1}^{\left \lfloor \frac{n}{dk} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{dk} \right \rfloor}[i*j*d\leq\left \lfloor \frac{n}{k^2} \right \rfloor]
\]

然后是非常神奇的缩小范围……

\[\sum_{k=1}^{\sqrt{n}}\mu(k)\sum_{d=1}^{\left \lfloor \frac{n}{k^2} \right \rfloor}\sum_{i=1}^{\left \lfloor \frac{n}{dk^2} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{n}{dk^2} \right \rfloor}[i*j*d\leq\left \lfloor \frac{n}{k^2} \right \rfloor]
\]

然后对于这个友好的范围直接枚举就可以了。

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

const int N=1000005,m=1000000;

int q[N],mb[N],tot;

long long a,b;

bool v[N];

long long wk(long long n)

{

	if(!n)

		return 0;

	long long re=0ll,tmp=0ll,a=sqrt(n);

	for(long long k=1;k<=a;k++)

		if(mb[k])

		{

			tmp=0;

			long long b=n/k/k;

			for(long long i=1;i*i*i<=b;i++)

			{

				for(long long j=i+1;j*j*i<=b;j++)

					tmp+=(b/(i*j)-j)*6+3;

				tmp+=(b/(i*i)-i)*3;

				tmp++;

			}

			re+=mb[k]*tmp;

		}

	return (re+n)/2;

}

int main()

{

	mb[1]=1;

	for(int i=2;i<=m;i++)

	{

		if(!v[i])

		{

			q[++tot]=i;

			mb[i]=-1;

		}

		for(int j=1;j<=tot&&i*q[j]<=m;j++)

		{

			int k=i*q[j];

			v[k]=1;

			if(i%q[j]==0)

			{

				mb[k]=0;

				break;

			}

			mb[k]=-mb[i];

		}

	}

	scanf("%lld%lld",&a,&b);

	printf("%lld\n",wk(b)-wk(a-1));

	return 0;

}

巴特西

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

最新文章

热门文章