书海扬帆的博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// luogu-judger-enable-o2
#include <bits/stdc++.h>
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 read() {
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("%lld\n", 1ll * p2[m[i]] % R * o[n[i]] % R * ksm(p1[m[i]], R - 2) % R);
return 0;
}


本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:725.9k