[SDOI 2008]沙拉公主的困惑

Description

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

Input

第一行为两个整数T，R。R<=10^9+10，T<=10000，表示该组中测试数据数目，R为模后面T行，每行一对整数N，M，见题目描述 m<=n

Output

共T行，对于每一对N，M，输出1至N！中与M！素质的数的数量对R取模后的值

Sample Input

1 11
4 2

Sample Output

HINT

数据范围：
对于100%的数据，1 < = N , M < = 10000000

题解

首先显然在区间 $[1, M!]$ 内与 $M!$ 互素的数个数为 $varphi(M!)$ 。

我们再考虑比 $M!$ 大的个数，值得注意的是我们存在这样一个性质：若 $x$ 与 $i$ （不）互质，则 $x+i$ 与 $i$ （不）互质。简要证明下：

现在我们证明对于整数 $x$ 若与 $i$ 互质，则 $x+i$ 也与 $i$ 互质。
采用反证法，我们假设 $gcd(x, i) = 1$ 但 $gcd(x+i, i) = b eq 1$ 。
容易发现： egin{cases} egin{aligned} x+i = bcdot k_1 \ i = b cdot k_2 end{aligned} end{cases} $k_1,k_2$ 均为整数。
所以 $x = (k_1-k_2)cdot b$ ，故 $gcd(x, i) = b eq 1$ ，与题设不符，原命题成立。
下证对于整数 $x$ 若与 $i$ 不互质，则 $x+i$ 也与 $i$ 不互质。
假设 $gcd(x, i) = b eq 1$ ， egin{cases} egin{aligned} x = bcdot k_1 \ i = b cdot k_2 end{aligned} end{cases}$k_1,k_2$ 均为整数。
所以 $x+i = (k_1+k_2)cdot b$ ，故 $gcd(x+i, i) = b eq 1$ ，原命题成立。

故该题的答案

egin{aligned} ans &= varphi(M!) cdot frac{N!}{M!} \ &= M! cdot prod_{pmid M!,p~is~a~prime} left( 1-frac{1}{p} ight)cdot frac{N!}{M!} \ &= N! cdot prod_{pmid M!,p~is~a~prime} frac{p-1}{p} end{aligned}

因为 $M!$ 素因数是连续的一段，所以我们只要统计 $[1, M!]$ 中的所有素数积的逆元，以及所有素数 $-1$ 的乘积即可。

ps:其实这道题是有 $bug$ 的，我们注意到用线性求逆元时求的数是不能大于等于模数的，而题面中并没有强调模数 $P$ 恒大于 $N$ 和 $M$ ，将错就做吧。

 1 //It is made by Awson on 2018.1.12
 2 #include <set>
 3 #include <map>
 4 #include <cmath>
 5 #include <ctime>
 6 #include <queue>
 7 #include <stack>
 8 #include <cstdio>
 9 #include <string>
10 #include <vector>
11 #include <cstdlib>
12 #include <cstring>
13 #include <iostream>
14 #include <algorithm>
15 #define LL long long
16 #define Max(a, b) ((a) > (b) ? (a) : (b))
17 #define Min(a, b) ((a) < (b) ? (a) : (b))
18 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
19 using namespace std;
20 const int N = 1e7;
21 void read(int &x) {
22     char ch; bool flag = 0;
23     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || 1); ch = getchar());
24     for (x = 0; isdigit(ch); x = (x<<1)+(x<<3)+ch-48, ch = getchar());
25     x *= 1-2*flag;
26 }
27 void write(int x) {
28     if (x > 9) write(x/10);
29     putchar(x%10+48);
30 }
31 
32 int t, n, m, p, inv[N+5], pro[N+5];
33 int prime[N+5], isprime[N+5], tot, A[N+5], B[N+5];
34 
35 void pre() {
36     pro[1] = inv[1] = 1; for (int i = 2; i <= N; i++) pro[i] = (LL)i*pro[i-1]%p, inv[i] = -(LL)p/i*inv[p%i]%p;
37     for (int i = 2; i <= N; i++) {
38     if (!isprime[i]) prime[++tot] = i;
39     for (int j = 1; j <= tot && i*prime[j] <= N; j++) {
40         isprime[i*prime[j]] = 1; if (!(i%prime[j])) break;
41     }
42     }
43     A[1] = B[1] = 1, A[prime[1]] = (prime[1]-1)%p, B[prime[1]] = inv[prime[1]]%p;
44     for (int i = 2; i <= tot; i++) A[prime[i]] = (LL)A[prime[i-1]]*(prime[i]-1)%p, B[prime[i]] = (LL)B[prime[i-1]]*inv[prime[i]]%p;
45     for (int i = 2; i <= N; i++) {if (!A[i]) A[i] = A[i-1]; if (!B[i]) B[i] = B[i-1]; }
46 }
47 void work() {
48     read(t), read(p);
49     pre(); while (t--) {
50     read(n), read(m); write(((LL)pro[n]*A[m]%p*B[m]%p+p)%p); putchar('
');
51     }
52 }
53 int main() {
54     work();
55     return 0;
56 }