1 #include
     
       2 #include
      
        3 #define ll long long 4 #define N 10000009 5 using namespace std; 6 int jie[N],ine[N],sum[N]; 7 int T,R,n,m,tot,zhan[N]; 8 bool mark[N]; 9 void exgcd(int a1,int a2,int &x,int &y)10 {11     if(!a2)12       {13         x=1;14         y=0;15         return;16       }17     exgcd(a2,a1%a2,x,y);18     int t=x;19     x=y;20     y=t-a1/a2*y;21 }22 int main()23 {24     scanf("%d%d",&T,&R);25     jie[1]=1;26     for(int i=2;i<=N-5;i++)27       jie[i]=(ll)jie[i-1]*i%R;28     for(int i=2;i<=N-5;i++)29       {30         if(!mark[i])31           {32             int y;33             exgcd(i,R,ine[i],y);34             ine[i]=(ine[i]+R)%R;35             zhan[++tot]=i;36           }37             for(int j=1;j<=tot&&zhan[j]*i<=N;j++)38               {39                 mark[zhan[j]*i]=1;40                 if(i%zhan[j]==0)41                   break;42               }43     }     44     sum[1]=1;45     for(int i=2;i<=N-5;i++)46       {47         sum[i]=sum[i-1];48         if(!mark[i])49           sum[i]=(ll)sum[i]*(i-1)%R*ine[i]%R;50       }51     for(;T;T--)52       {53         scanf("%d%d",&n,&m);54         printf("%d\n",(ll)jie[n]*sum[m]%R);55       }56     return 0;57 }
      
     

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

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