前言
题目传送门 Luogu P2155 [SDOI2008] 沙拉公主的困惑
非常恶心的一道题，但是认真地写完会非常有收获。
需要掌握欧拉函数、乘法逆元。
题意
多测。求出 \([1, n!]\) 范围中与 \(m!\) 互质的整数个数。答案对 \(r\) 取模。
\(1\le m\le n\le 10^7, \ 2\le r\le 10^9+10\) 且保证 \(r\) 是质数。
思路
首先，我们知道 \(\gcd(a, b) = \gcd(a+kb, b),\ k\in\mathbb{N}\) 。这其实也就是辗转相除法的原理，我就不多赘述。
这个定理告诉我们什么呢？由于 \(m!\mid n!\) ，我们可以从 \(1\) 开始每 \(m\) 个数划为一组，那么一共有 \(\frac{n!}{m!}\) 组。由上面的定理可知，每组中与 \(m!\) 互质的数的数量是相同的。所以我们就能得到一个答案的表达式：
那么看起来我们只要预处理 \(1\le n \le 10^7\) 的 \(n!\) 及其逆元和 \(\varphi(n!)\) 即可。不过直接用通项公式计算 \(\varphi(n!)\) 听起来有点天方夜谭。我们不妨来试着用递推的方式来找一个 \(O(n)\) 的方法。
首先观察到 \(n!\) 的所有质因数就是 \(1\sim n\) 的所有质数。于是我们有：
由于 \(n!=(n-1)!\cdot n\) ，我们可以分类讨论：
-
若 \(n\) 是质数，则 \(n!\) 相比于 \((n-1)!\) 多了一个质因子。所以连乘式中就多了一项。我们可以得到 \(\varphi (n!) = \varphi((n-1)!) \cdot n\cdot \frac{n-1}{n} = \varphi((n-1)!)\cdot (n-1)\) 。
-
若 \(n\)是合数，则 \(n!\) 相比于 \((n-1)!\) 质因数不变。所以有 \(\varphi(n!) = \varphi((n-1)!)\cdot n\) 。
不难看出，我们需要在遍历 \(1\sim n\) 的同时判断 \(i\) 的素性。那我们直接在线性筛的同时求出即可。
我们还需要知道的是如何快速求出 \(n!\) 在模 \(r\) 意义下的逆元。显然，对每个 \(n!\) 都做快速幂是不现实的。不过我们同样有递推的方法。请看下面的推导：
所以 \(n!^{-1}\) 可由 \((n+1)!^{-1}\) 得到。我们可以先用一次费马小定理和快速幂求得 \(N=10^7\) 模 \(r\) 的乘法逆元，然后倒推回每个数的。
看起来问题已经结束力！但是并没有。试想如果 \(n\ge r\) ，那么 \(n!\) 就会有 \(r\) 这个质因子。这时我们再计算 \(n!\) 的逆元，就会发现逆元不存在了。正确的做法是，我们回到 \(ans\) 的计算式：
其中若 \(m\) 也 \(\ge r\) ，则分母上的 \(\prod p\) 也可以提供一个 \(r\) ，它们可以约去。
你一定会有疑问：如果 \(m<r\) 或者 \(n\ge 2r\) ，不就约不干净了吗？是的，所以这两种情况答案是 \(0\) ，我们先特判掉；剩下的情况就是能约干净的。那么我们就可以预处理在求阶乘及其逆元时，遇到 \(r\) 的倍数就跳过，这样就不会出现没有逆元的情况了。
代码
#include<iostream>
#define fastio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MIKU 0
using namespace std;const int N = 1e7;int t, r, n, m;
int fac[N+5], phi[N+5], inv[N+5], p[N+5];
bool np[N+5];int qpow(int a, int n) {int ans = 1;a %= r;while(n > 0) {if(n & 1) ans = 1ll * ans * a % r;a = 1ll * a * a % r; n >>= 1;}return ans;
}void init() {fac[0] = fac[1] = phi[1] = 1;for(int i=1; i<=N; i++) fac[i] = 1ll * fac[i-1] * (i%r ? i : 1) % r;inv[N] = qpow(fac[N], r-2);for(int i=N-1; i>=0; i--) inv[i] = 1ll * inv[i+1] * ((i+1)%r ? i+1 : 1) % r;for(int i=2; i<=N; i++) {if(!np[i]) p[++p[0]] = i, phi[i] = 1ll * phi[i-1] * (i-1) % r;else phi[i] = 1ll * phi[i-1] * i % r;for(int j=1; j<=p[0] && 1ll*i*p[j]<=N; j++) {np[i * p[j]] = 1;if(i % p[j] == 0) break;}}
}int main() {fastio;cin>>t>>r;init();while(t--) {cin>>n>>m;if((n >= r && m < r) || n >= 2 * r) {cout<<0<<'\n'; continue;}cout<<1ll * (1ll * fac[n] * phi[m] % r) * inv[m] % r<<'\n';}return MIKU;
}