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

前言

题目传送门 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!\) 互质的数的数量是相同的。所以我们就能得到一个答案的表达式：

\[ans = \frac{n!}{m!}\cdot \varphi(m!)\]
那么看起来我们只要预处理 \(1\le n\le 10^7\) 的 \(n!\) 及其逆元和 \(\varphi(n!)\) 即可。不过直接用通项公式计算 \(\varphi(n!)\) 听起来有点天方夜谭。我们不妨来试着用递推的方式来找一个 \(O(n)\) 的方法。
首先观察到 \(n!\) 的所有质因数就是 \(1\sim n\) 的所有质数。于是我们有：

\[\varphi(n!) = n!\cdot \prod_{p\in \mathbb{P} \& p\le n} \frac{p-1}{p}\]
由于 \(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!\) 都做快速幂是不现实的。不过我们同样有递推的方法。请看下面的推导：

\[\begin{align*}(n+1)!&=n!\cdot(n+1) &\ (\ \bmod\ p\ )\\(n+1)!^{-1} &= n!^{-1}\cdot (n+1)^{-1} &\ (\ \bmod\ p\ )\\n!^{-1} &= (n+1)!^{-1}\cdot (n+1) &\ (\ \bmod\ p\ )\end{align*}\]
所以 \(n!^{-1}\) 可由 \((n+1)!^{-1}\) 得到。我们可以先用一次费马小定理和快速幂求得 \(N=10^7\) 模 \(r\) 的乘法逆元，然后倒推回每个数的。
看起来问题已经结束力！但是并没有。试想如果 \(n\ge r\) ，那么 \(n!\) 就会有 \(r\) 这个质因子。这时我们再计算 \(n!\) 的逆元，就会发现逆元不存在了。正确的做法是，我们回到 \(ans\) 的计算式：

\[ans = n!\cdot \prod_{p\in \mathbb{P} \& p\le m} \frac{p-1}{p}\]
其中若 \(m\) 也 \(\ge r\) ，则分母上的 \(\prod p\) 也可以提供一个 \(r\) ，它们可以约去。

你一定会有疑问：如果 \(m 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=0; i--) inv = 1ll * inv[i+1] * ((i+1)%r ? i+1 : 1) % r;        for(int i=2; i>r;        init();        while(t--) {                cin>>n>>m;                if((n >= r && m < r) || n >= 2 * r) {cout