1 11

4 2

1

### 分析

$\phi \left(m!\right)=m!\left(1-\frac{1}{{p}_{1}}\right)...\left(1-\frac{1}{{p}_{k}}\right)$，可知
$ans=n!\ast \left(1-\frac{1}{{p}_{1}}\right).....\left(1-\frac{1}{{p}_{k}}\right)$
$f\left(n\right)=n!$ $g\left(m\right)=\left(1-\frac{1}{{p}_{1}}\right).....\left(1-\frac{1}{{p}_{k}}\right)$，分别在线性时间内预处理出来即可。

### 代码如下

#include <bits/stdc++.h>
#define N 10000005
#define LL long long
using namespace std;
int x[N], p[N], inv[N], fac[N], w[N], cnt, P;
LL z = 1, t;
void exgcd(int a, int b, int &x, int &y){
if(!b) x = 1, y = 0;
else{
exgcd(b, a % b, y, x);
y -= a / b * x;
}
}
int main(){
int i, j, n, m, T, las, a, b;
scanf("%d%d", &T, &P);
for(i = 2; i <= 10000000; i++){
if(!x[i]) x[i] = p[++cnt] = i;
for(j = 1; j <= cnt; j++){
t = z * p[j] * i;
if(t > 10000000) break;
x[t] = p[j];
if(i % p[j] == 0) break;
}
}
for(fac[0] = i = 1; i <= 10000000; i++) fac[i] = z * fac[i-1] * i % P;
w[1] = inv[1] = 1;
//for(i = 2; i <= 10000000; i++) inv[i] = z * (P - P / i) * inv[P % i] % P;
for(i = 1; i <= cnt; i++){
exgcd(p[i], P, a, b);
a = (a % P + P) % P;
inv[p[i]] = a;
}
for(i = 2; i <= 10000000; i++){
w[i] = w[i-1];
if(x[i] == i) w[i] = z * w[i-1] * (i - 1) % P * inv[i] % P;
}
while(T--){
scanf("%d%d", &n, &m);
printf("%d\n", z * fac[n] * w[m] % P);
}
return 0;
}