「BZOJ2186」[SDOI2008]沙拉公主的困惑

Description

大富翁国因为通货膨胀,以及假钞泛滥,政府决定推出一项新的政策:现有钞票编号范围为11NN的阶乘,但是,政府只发行编号与M!M!互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在,请你帮助沙拉公主解决这个问题,由于可能张数非常大,你只需计算出对RR取模后的答案即可。RR是一个质数。

Input

第一行为两个整数TTRR。表示该组中测试数据数目,R为模后面TT行,每行一对整数NNMM,见题目描述 mnm\leq n

Output

TT行,对于每一对NNMM,输出11N!N!中与M!M!素质的数的数量对RR取模后的值

Sample Input

1
2
1 11
4 2

Sample Output

1
1

HINT

R109+10,T10000R\leq 10^9+10,T\leq 10000
对于100%100\%的数据,1N,M100000001 \leq N , M \leq 10000000

Solution

根据更相减损术,如果(x,y)=1(x,y)=1,那么(x+ky,y)=1(x+ky,y)=1也成立。
那么可以把n!n!分成(0,m!],(m!,2m!],(2m!,3m!](km!,(k+1)m!](0,m!],(m!,2m!],(2m!,3m!]\cdots (km!,(k+1)m!]
答案就是n!m!ϕ(m!)\frac{n!}{m!}\phi(m!)
ϕ(m!)=m!(11pi)\phi(m!)=m!\prod(1-\frac{1}{p_i}),代入上面答案就是n!(11pi)n!\prod(1-\frac{1}{p_i})
注意:必须要代入,因为a%pb%p=ab%p\frac{a\%p}{b\%p}=\frac{a}{b}\%p不一定成立。
注意ϕ(m)=ϕ(m!)\phi(m)=\phi(m!)不一定成立,所有与m!m!的质因子显然就是[1,m][1,m]里的质数了。

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
47
48
49
50
51
52
53
54
55
56
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e7 + 666;
ll p;
int n, m;
bool vis[N];
int b[820420], tot;
int fac[N], ans[N], inv[N];
void init() {
ans[1] = vis[1] = 1;
inv[1] = 1;
for(int i = 2; i <= 1e7; ++i) {
if(!vis[i])
b[++tot] = i;
for(int j = 1; j <= tot && b[j] <= 1e7 / i; ++j) {
vis[i * b[j]] = 1;
if(i % b[j] == 0) break;
}
}
fac[1] = 1;
for(int i = 2; i <= 1e7 && i < p; ++i) {
fac[i] = (ll)fac[i - 1] * i % p;
inv[i] = (ll)(p - p / i) * inv[p % i] % p;
}
for(int i = 2; i <= 1e7; ++i) {
ans[i] = ans[i - 1];
if(!vis[i]) ans[i] = (ll)ans[i] * (i - 1) %p * inv[i] % p;
}

}

int main() {
int T = read(); p = read();
init();
while(T--) {
n = read(), m = read();
writeln((ll)fac[n] * ans[m] % p);
}
return 0;
}

TLE,但是不会被Hack的代码:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e7 + 666;
ll p;
int n, m;
bool vis[N];
int b[820420], tot;
int fac[N], ans[N];
int inv[N];
void init() {
ans[1] = vis[1] = 1;
inv[1] = 1;
for(int i = 2; i <= 1e7; ++i) {
ans[i] = ans[i - 1];
inv[i] = (ll)(p -(p / i)) * inv[p % i] % p;
if(!vis[i]) {
if(i == p) ans[i] = (ll)ans[i] * (i - 1) %p;
else
ans[i] = (ll)ans[i] * (i - 1) %p * inv[i] % p;
b[++tot] = i;
}
for(int j = 1; j <= tot && b[j] <= 1e7 / i; ++j) {
vis[i * b[j]] = 1;
if(i % b[j] == 0) break;
}
}
fac[1] = 1;
for(int i = 2; i <= 1e7; ++i) {
if(i == p && !vis[p]) fac[i] = fac[i - 1];
else
fac[i] = (ll)fac[i - 1] * i % p;
}
}

int main() {
int T = read(); p = read();
init();
while(T--) {
n = read(), m = read();
if(n >= p && m >= p || n < p && m < p)
writeln((ll)fac[n] * ans[m] % p);
else
if(n >= p)
writeln((ll)fac[n] * p %p * ans[m] % p);
else
writeln((ll)fac[n] * ans[m] %p * inv[p] %p);
}
return 0;
}