[SDOI2008]沙拉公主的困惑

1.丑话说在前头

此题解只是因为Luogu的数据过水，没有去讨论不互质时不能使用逆元的情况。

2.思路

首先我们可以知道(ecause(a,m)=1 herefore (a+m,m)=1,ecause(a,m) ot=1 herefore(a+m,m) ot=1),故这是一个成周期性的的东西。又因为(phi(m!))表示比他小的互质个数，所以题目求解的答案是

[egin{align} &frac{n!}{m!}*phi(m!)\=&frac{n!}{m!}*m!(1-frac{1}{p_1})(1-frac{1}{p_2})...(1-frac{1}{p_m})\=&n!(1-frac{1}{p_1})(1-frac{1}{p_2})...(1-frac{1}{p_m}) end{align} ]

其中(p_i)为(m!)的一个质因子。（上面运用的是欧拉函数的推导）。由于答案很大，又要对r取模，又有分数，所以我们用乘法逆元（此处并没有讨论是否互质，是笔者的失误）。对于多组数据，为了不超时，我们直接跑一遍最大的欧拉筛就行。在欧拉筛的同时处理出不同的n！和(frac{p_i-1}{p_i})之间的乘积以及(p_i)的逆元，由于筛出来的质数是从小到大，求的又是m!，所以可以用递推。

3.代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=10000005;
ll t,r,n,m;
ll prime[MAXN],tot;
ll inv[MAXN]={1,1};
bool vis[MAXN];
ll u[MAXN]={1,1};
ll bn,bm;
ll jc[MAXN]={1,1};
void checkp(ll maxn){
	vis[1]=vis[0]=1;
	for(ll i=2;i<=maxn;++i){
		jc[i]=(jc[i-1]*i)%r;
		inv[i]=((r-r/i)*inv[r%i])%r;
		if(!vis[i]){
			prime[++tot]=i;
			u[i]=(((u[i-1]*(i-1))%r*inv[i]+r)%r+r)%r;
		}
		else u[i]=u[i-1];
		for(ll j=1;j<=tot&&i*prime[j]<=maxn;++j){
			vis[i*prime[j]]=1;
			if(!(i%prime[j]))break;
		}
	}
	return ;
}
ll gcd(ll a,ll b){
	return a?gcd(b%a,a):b;
}
int main(){
	cin>>t>>r;
	checkp(MAXN);
	while(t--){
		cin>>n>>m;
		cout<<(jc[n]*u[m]+r)%r<<endl;	
	}
	return 0;
}