bzoj 2186: [Sdoi2008]沙拉公主的困惑

时间:2023-03-09 03:43:30
bzoj 2186: [Sdoi2008]沙拉公主的困惑
 #include<cstdio>
#include<iostream>
#define ll long long
#define N 10000009
using namespace std;
int jie[N],ine[N],sum[N];
int T,R,n,m,tot,zhan[N];
bool mark[N];
void exgcd(int a1,int a2,int &x,int &y)
{
if(!a2)
{
x=;
y=;
return;
}
exgcd(a2,a1%a2,x,y);
int t=x;
x=y;
y=t-a1/a2*y;
}
int main()
{
scanf("%d%d",&T,&R);
jie[]=;
for(int i=;i<=N-;i++)
jie[i]=(ll)jie[i-]*i%R;
for(int i=;i<=N-;i++)
{
if(!mark[i])
{
int y;
exgcd(i,R,ine[i],y);
ine[i]=(ine[i]+R)%R;
zhan[++tot]=i;
}
for(int j=;j<=tot&&zhan[j]*i<=N;j++)
{
mark[zhan[j]*i]=;
if(i%zhan[j]==)
break;
}
}
sum[]=;
for(int i=;i<=N-;i++)
{
sum[i]=sum[i-];
if(!mark[i])
sum[i]=(ll)sum[i]*(i-)%R*ine[i]%R;
}
for(;T;T--)
{
scanf("%d%d",&n,&m);
printf("%d\n",(ll)jie[n]*sum[m]%R);
}
return ;
}

答案为n!/m!*phi(m!) 化简后就变成了n!*(p1-1)/p1*(p2-1)/p2*......

预处理n!与后面那些数,答案就可以很快求出来。当然除的话要用逆元。