「巴蜀中学NOIP2017模拟D4T3」心灵治愈 - 莫比乌斯反演/容斥原理

题目大意

求出$a_1x_1+a_2x_2+\cdots+a_nx_n+a_{n+1}M=1$的方案数，其中$x_i\le M$。

---

题目分析

根据裴蜀定理，可得题目等价为求$\gcd(x_1,x_2,\ldots,x_n,M)=1$的方案数。

开始反演：

$$Ans=\sum_{x_1=1}^{M}\sum_{x_2=1}^{M}\cdots\sum_{x_n=1}^{M}\sum_{d\mid x_1,d\mid x_2,\ldots,d\mid x_n}\mu(d)$$ $$Ans=\sum_{d\mid M}^{M}\mu(d)(\frac{M}{d})^n$$

然后我们就可以愉悦地筛出$\sqrt{M}$以内的莫比乌斯函数，然后枚举约数即可，注意可能会有一个$\sqrt{M}$以外的质数，显然其$\mu$为$-1$。

然而这样只能得到$90$分，因为当$M$很大的时候，Memory Limit Exceeded了（$pointedpoints$：“Menci Limit Exceeded”）。

$80\rightarrow90$分的数据提示我们，可以通过分解考虑。

$$Ans=\sum_{d\mid M}^{M}\mu(d)(\frac{M}{d})^n=f(M)$$

不难发现，$f(i)$是一个积性函数，因为积性函数与积性函数的狄利克雷卷积依然是积性函数。

因此：

$$f(M)=f(p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k})=f(p_1^{a_1})f(p_2^{a_2})\cdots f(p_k^{a_k})$$ $$f(p^k)=\sum_{i=0}^{k}\mu(p^i)(\frac{p^k}{p^i})^n$$

因此当$i\ge2$的时候，$\mu(p^i)=0$，故对于每一个素数的幂，我们仅需要计算$i=0,1$即可，其$\mu$分别为$1,-1$。

这样我们就不需要线性筛了，时间空间都有很大的优势。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
typedef long long LL;
inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
const LL mod=1000000007;
LL Quick_Pow(LL a,LL b) {
	LL ans=1;
	a%=mod;
	while(b) {
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
LL n,m,ans=1;
int main() {
	n=Get_Int();
	m=Get_Int();
	for(int i=2; i<=sqrt(m); i++)
		if(m%i==0) {
			LL tmp=1;
			while(m%i==0)m/=i,tmp*=i;
			ans=(ans*(Quick_Pow(tmp,n)-Quick_Pow(tmp/i,n))%mod+mod)%mod;
		}
	if(m!=1)ans=(ans*(Quick_Pow(m,n)-Quick_Pow(1,n))%mod+mod)%mod;
	printf("%lld\n",ans%mod);
	return 0;
}