BZOJ2186 SDOI2008 沙拉公主的困惑 逆元+欧拉函数

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN=10000000+2;
long long T,R,N,M,fac[MAXN],prime[MAXN],inv[MAXN],cnt,a[MAXN];
bool flag[MAXN];

void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return;
    }

    exgcd(b,a%b,x,y);

    int t=x;
    x=y,y=t-a/b*y;
}

int Calc_Inv(int a,int p){
    int x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
}

int main(){
    cin >> T >> R;

    fac[0]=1;
    for(int i=1;i<=MAXN;i++) fac[i]=(fac[i-1]*i)%R;

    for(int i=2;i<=MAXN;i++){
        if(!flag[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt && prime[j]*i<=MAXN;j++){
            flag[i*prime[j]]=1;
            if(!(i%prime[j])) break;
        }
    }

    inv[1]=1;
    for(int i=2;i<=MAXN;i++) inv[i]=Calc_Inv(i,R);

    a[0]=a[1]=1;
    for(int i=2;i<=MAXN;i++)
        if(!flag[i]) a[i]=a[i-1]*(i-1)%R*inv[i%R]%R;
        else a[i]=a[i-1];

    while(T--){
        cin >> N >> M;
        cout << (fac[N]*a[M])%R << endl;
    }

    return 0;
}