题解：P2155 [SDOI2008] 沙拉公主的困惑

· · 题解

题目大意

题意为求 n! 以内与 m! 互质的数的个数（n \ge m）。

思路

我们可以发现一个神奇的性质，由于 n \ge m，那么 m! \mid n!。然后 m! 内与 m! 互质的数的个数为 \varphi(m!)，然后 n! 又为 m! 的倍数，这时候就能猜一猜 n! 内与 m! 互质的数的个数为 \frac{\varphi(m!)n!}{m!}，然后再严谨证明。

推论 1：若 y \mid x，则 1 至 x 与 y 互质的正整数个数为 \frac{\varphi(y)x}{y}。

证明：

先简化，我们知道 1 至 y 内与 y 互质的数的个数为 \varphi(y)。

假设 i(1 \le i \lt y) 与 y 互质，根据 gcd(a, b) = gcd(a + kb, b)，将 i 带入 a，y 带入 b，即 gcd(i, y) = gcd(i + ky, y)。

此时 gcd(i, y) = 1，即 gcd(i + ky, y) = 1，即 i + ky 与 y 互质，即 i 加上任意 y 的倍数均与 y 互质。

再推广，那么 1 至 x 中共有多少个 i + ky 呢？

由于 i + ky \le x，即 0 \le k \le \frac{x - i}{y}，由于 k 为整数，则共有 \lfloor \frac{x - i}{y} \rfloor + 1 = \lfloor \frac{x}{y} - \frac{i}{y} \rfloor + 1 个 k。

由于 y \mid x, 1 \le i \lt y，那么 \frac{x}{y} 为整数且 0 \lt \frac{i}{y} \lt 1，\lfloor \frac{x}{y} - \frac{i}{y} \rfloor + 1 = (\frac{x}{y} - 1) + 1 = \frac{x}{y}。

所以对于每个 i，在 1 到 x 中共有 \frac{x}{y} 个 i + ky。

又由于共有 \varphi(y) 个 i，则 1 至 x 内共有 \frac{\varphi(y)x}{y} 个数与 y 互质。

你可能会说除了 i + ky 形式的数，可能还有其他的数与 y 互质，我们再来证明一下这不可能成立：

若一个数 n 与 y 互质，那么 gcd(n, y) = 1。

根据欧几里得算法，可得 gcd(n \bmod y, y) = gcd(n, y) = 1。

这时 n \bmod y 一定为其中一个 i，否则 gcd(n \bmod y, y) \not = 1。

这就说明一个与 y 互质的数一定可以被写成 i + ky 的形式。

证毕。

回到题目，此时答案即为 \frac{\varphi(m!)n!}{m!}，然后我们就可以直接做了，预处理 n! 及其逆元，以及 \varphi(n!)。

那么怎么得到 \varphi(n!) 呢？考虑从 \varphi((n - 1)!) 递推过来。

注意到 n! 有一个性质，就是其为所有不大于 n 的质数的倍数。也就是说 \varphi(n!) 可以写成：

\displaystyle \prod_{p \in \mathbb{P},p \mid n} \varphi(p^k)

其中所有的 k \ge 1，分类讨论一下：

当 n \in \mathbb{P} 时，\varphi(n!) = \varphi((n - 1)!) \times (n − 1)。

当 n \not \in \mathbb{P} 时，\varphi(n!)=\varphi((n - 1)!) \times n。

于是可以递推得到 \varphi(n!)。

细节

预处理后，除法用逆元处理即可，提交以后，恭喜你，炸了。

因为题目中并没有说明 r \gt m，所以逆元可能会爆炸！

所以，在预处理时，我们要将所有数写成 a \times r^b(r \nmid a) 的形式，用两个数组分别存储 a 和 b。

当两数相乘时将 a 相乘，将 b 相加，当两数相除时用除数的 a 乘上倍数数 a 的逆元，将 b 相减即可。

最后，如果答案的 b \gt 0 那么答案 \bmod r 的结果即为 0，输出 0 即可。

反之，如果答案的 b = 0，则输出答案的 a 即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int qpow(int a, int b, int mod){ // 快速幂 
    int ans = 1, t = a;
    for(; b > 0; b >>= 1){
        if(b & 1) ans = ((ll)ans * t) % mod;
        t = ((ll)t * t) % mod;
    }
    return ans;
}

const int N = 10000050;

int t, r, n, m, u, k;
int phia[N], phib[N]; // phia(i)的a和b
int tmsa[N], tmsb[N]; // i!的a和b 
bool vis[N];

int main(){
    cin >> t >> r;
    vis[1] = 1;
    // 埃氏筛筛质数 
    for(int i = 1; i < N; i ++)
        if(!vis[i])
            for(int j = i; (ll)j * i < N; j ++)
                vis[i * j] = 1;
    // 预处理 
    phia[0] = 1; phib[0] = 0; tmsa[0] = 1; tmsb[0] = 0;
    for(int i = 1; i < N; i ++){
        // 处理阶乘 
        u = i, k = 0;
        while(u % r == 0) u /= r, k ++; // 将i中所有的r除出来 
        tmsa[i] = ((ll)tmsa[i - 1] * u) % r; /*将a相乘*/ tmsb[i] = tmsb[i - 1] + k /*将b相加*/;
        // 处理phi前缀积 
        u = (vis[i] ? i : i - 1), k = 0;
        while(u % r == 0) u /= r, k ++; // 将i中所有的r除出来
        phia[i] = ((ll)phia[i - 1] * u) % r; /*将a相乘*/ phib[i] = phib[i - 1] + k /*将b相加*/;
    }
    while(t --){
        scanf("%d%d", &n, &m);
        int ans = (ll)tmsa[n] * phia[m] % r * qpow(tmsa[m], r - 2, r) % r; // 求出答案的a 
        if(tmsb[n] + phib[m] - tmsb[m] == 0) printf("%d\n", ans); // 若答案的b为零，输出ans的a 
        else printf("0\n"); // 否则答案为r的倍数，输出0 
    }
    return 0;
}