[bzoj2186] [Sdoi2008]沙拉公主的困惑

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 #define ll long long
 5 using namespace std;
 6 const int maxn=10023333,mx=1e7;
 7 int p[maxn],pnum;
 8 int jc[maxn],f[maxn];
 9 bool gg[maxn];
10 int i,j,k,n,m,modd;
11  
12 int ra;char rx;
13 inline int read(){
14     rx=getchar(),ra=0;
15     while(rx<‘0‘||rx>‘9‘)rx=getchar();
16     while(rx>=‘0‘&&rx<=‘9‘)ra*=10,ra+=rx-48,rx=getchar();return ra;
17 }
18  
19 inline int poi(int a,int b){
20     int c=1;
21     while(b){
22         if(b&1)c=1ll*c*a%modd;
23         b>>=1,a=1ll*a*a%modd;
24     }return c;
25 }
26 inline void getp(){
27     register int i,j;
28     for(i=2;i<=mx;i++){
29         if(!gg[i])p[++pnum]=i;
30         for(j=1;j<=pnum&&1ll*p[j]*i<=mx;j++){
31             gg[p[j]*i]=1;
32             if(!i%p[j])break;
33         }
34     }
35 }
36 inline void getphi(){
37     f[1]=1;
38     for(register int i=2;i<=mx;i++)if(!gg[i])f[i]=1ll*f[i-1]*(i-1)%modd;
39     else f[i]=1ll*f[i-1]*i%modd;
40 }
41 int main(){int t;
42     t=read(),modd=read();
43     getp(),
44     getphi();
45     for(i=jc[0]=1;i<=mx;i++)jc[i]=1ll*jc[i-1]*i%modd;
46     while(t--){
47         n=read(),m=read();
48         printf("%lld\n",1ll*f[m]*jc[n]%modd*poi(jc[m],modd-2)%modd);
49     }
50 }
51