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\) ，我们可以分类讨论：

1. 若 \(n\) 是质数，则 \(n!\) 相比于 \((n-1)!\) 多了一个质因子。所以连乘式中就多了一项。我们可以得到 \(\varphi (n!) = \varphi((n-1)!) \cdot n\cdot \frac{n-1}{n} = \varphi((n-1)!)\cdot (n-1)\) 。

2. 若 \(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<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;
}