逆元-bzoj2185/洛谷p2155-sdoi2008-沙拉公主的困惑

using namespace std;
const int MAXN = 1e7 + 15;
int n[MAXN], m[MAXN], T, inv[MAXN], p1[MAXN], p2[MAXN], prime[MAXN], flag[MAXN], o[MAXN];
int Max, R;
inline int () {
    char ch = getchar(); int u = 0, f = 1;
    while (!isdigit(ch)) {if (ch == '-')f = -1; ch = getchar(); }
    while (isdigit(ch)){u = u * 10 + ch - 48; ch = getchar(); }return u * f;
}
inline int ksm(long long x, int k){
    long long cnt = 1;
    while (k){
        if (k & 1)cnt = cnt * x % R;
        x = x * x % R;k >>= 1;
    }
    return cnt;
}
signed main(){
    T = read(); R = read(); inv[1] = 1; o[1] = 1;
    for (register int i = 1; i <= T; i++) {
        n[i] = read(); m[i] = read();
        Max = max (Max, max (n[i], m[i]));
    }
    for (register int i = 2; i <= Max + 10; i++) {
        if (!flag[i]) prime[++prime[0]] = i;
        o[i] = 1ll * o[i - 1] * i % R;
        for (register int j = 1; j <= prime[0] && prime[j] * i <= Max + 10; j++){
            flag[prime[j] * i] = 1;
            if (i % prime[j] == 0)break;
        }
    }
    int cnt = 1;
    p1[0] = 1; p2[0] = 1; prime[++prime[0]] = 1e9 + 10;
    for (register int i = 1; i <= Max + 10; i++){
        p1[i] = p1[i - 1]; p2[i] = p2[i - 1];
        while (prime[cnt] <= i){
            p1[i] = 1ll * p1[i] * prime[cnt] % R;
            p2[i] = 1ll * p2[i] * (prime[cnt] - 1) % R; cnt++;
        }
    }
    for (register int i = 1; i <= T; i++)
        printf("%lldn", 1ll * p2[m[i]] % R * o[n[i]] % R * ksm(p1[m[i]], R - 2) % R);
    return 0;
}