BZOJ 2186 [Sdoi2008]沙拉公主的困惑

题目大意

求1~N!中与M!素质的数的数量对R取模后的值.

用到的公式：$\sum\limits_{i=1}^{M}[\gcd(i,N)=1] = \varphi(N) \frac{M}{N} (N|M)$

理由：因为$\gcd(i+N,N) = \gcd(i,N)$，所以一个M之内的数如果与M互质，那么它加上N的倍数与N也是互质的，对于N的倍数M而言就有$\frac{M}{N}$个倍数。

另一个公式：$inv[i]≡(p-{\lfloor{p\over i}\rfloor})*inv[p\mod i]$

理由：证明见博客，这里作为结论使用。

这题求的就是$\varphi(M!) \frac{N!}{M!}$.

因为$\varphi(N)=N\prod\frac{P_i-1}{P_i} (P_i|N,\gcd(P_i,N)=1)$，所以$\varphi(M!) \frac{N!}{M!} = \frac{N!}{M!} M!\prod\frac{P_i-1}{P_i} = N! \prod\frac{P_i-1}{P_i} = N! \prod (P_i-1) \prod\frac{1}{P_i}$.

因为是模意义下的运算所以对于需要处理的就是$\prod (P_i-1)$的前缀积和$\prod\frac{1}{P_i}$的逆元的前缀积。这两个都可以线性筛。筛法的公式见上。

#include <cstdio>
#include <algorithm>
using namespace std;
#define R register
#define N 10000000
int P,cnt;
int fac[N+1],prm[N+1],res[N+1],rev[N+1];
bool v[N+1];
void init()
{
	fac[1]=rev[1]=res[1]=1;
	for(int i=2;i<=N;++i)
	{
		rev[i]=1ll*(P-P/i)*rev[P%i]%P;
		fac[i]=1ll*(fac[i-1]*i)%P;
		if(!v[i]) prm[++cnt]=i,res[i]=1ll*res[i-1]*(i-1)%P*rev[i%P]%P;
		else res[i]=res[i-1];
		for(int j=1;j<=cnt&&i*prm[j]<=N;++j)
		{
			v[i*prm[j]]=true;
			if(!(i%prm[j])) break;
		}
	}
}
int main()
{
	R int T,n,m;
	scanf("%d%d",&T,&P);
	init();
	while(T--)
	{
		scanf("%d%d",&n,&m);
		printf("%d\n",fac[n]*res[m]%P);
	}
	return 0;
}