专栏文章

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

JJHR100330
P2155题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@miowi257
此快照首次捕获于
2025/12/03 02:17
3 个月前
此快照最后确认于
2025/12/03 02:17
3 个月前
查看原文

题目大意

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

思路

我们可以发现一个神奇的性质，由于 n≥mn \ge m，那么 m!∣n!m! \mid n!。然后 m!m! 内与 m!m! 互质的数的个数为 φ(m!)\varphi(m!)，然后 n!n! 又为 m!m! 的倍数，这时候就能猜一猜 n!n! 内与 m!m! 互质的数的个数为 φ(m!)n!m!\frac{\varphi(m!)n!}{m!}，然后再严谨证明。
推论 11：若 y∣xy \mid x，则 11 至 xx 与 yy 互质的正整数个数为 φ(y)xy\frac{\varphi(y)x}{y}。
证明：
先简化，我们知道 11 至 yy 内与 yy 互质的数的个数为 φ(y)\varphi(y)。
假设 i(1≤i<y)i(1 \le i \lt y) 与 yy 互质，根据 gcd(a,b)=gcd(a+kb,b)gcd(a, b) = gcd(a + kb, b)，将 ii 带入 aa，yy 带入 bb，即 gcd(i,y)=gcd(i+ky,y)gcd(i, y) = gcd(i + ky, y)。
此时 gcd(i,y)=1gcd(i, y) = 1，即 gcd(i+ky,y)=1gcd(i + ky, y) = 1，即 i+kyi + ky 与 yy 互质，即 ii 加上任意 yy 的倍数均与 yy 互质。
再推广，那么 11 至 xx 中共有多少个 i+kyi + ky 呢？
由于 i+ky≤xi + ky \le x，即 0≤k≤x−iy0 \le k \le \frac{x - i}{y}，由于 kk 为整数，则共有 ⌊x−iy⌋+1=⌊xy−iy⌋+1\lfloor \frac{x - i}{y} \rfloor + 1 = \lfloor \frac{x}{y} - \frac{i}{y} \rfloor + 1 个 kk。
由于 y∣x,1≤i<yy \mid x, 1 \le i \lt y，那么 xy\frac{x}{y} 为整数且 0<iy<10 \lt \frac{i}{y} \lt 1，⌊xy−iy⌋+1=(xy−1)+1=xy\lfloor \frac{x}{y} - \frac{i}{y} \rfloor + 1 = (\frac{x}{y} - 1) + 1 = \frac{x}{y}。
所以对于每个 ii，在 11 到 xx 中共有 xy\frac{x}{y} 个 i+kyi + ky。
又由于共有 φ(y)\varphi(y) 个 ii，则 11 至 xx 内共有 φ(y)xy\frac{\varphi(y)x}{y} 个数与 yy 互质。
你可能会说除了 i+kyi + ky 形式的数，可能还有其他的数与 yy 互质，我们再来证明一下这不可能成立：
若一个数 nn 与 yy 互质，那么 gcd(n,y)=1gcd(n, y) = 1。
根据欧几里得算法，可得 gcd(n mod y,y)=gcd(n,y)=1gcd(n \bmod y, y) = gcd(n, y) = 1。
这时 n mod yn \bmod y 一定为其中一个 ii，否则 gcd(n mod y,y)≠1gcd(n \bmod y, y) \not = 1。
这就说明一个与 yy 互质的数一定可以被写成 i+kyi + ky 的形式。
证毕。
回到题目，此时答案即为 φ(m!)n!m!\frac{\varphi(m!)n!}{m!}，然后我们就可以直接做了，预处理 n!n! 及其逆元，以及 φ(n!)\varphi(n!)。
那么怎么得到 φ(n!)\varphi(n!) 呢？考虑从 φ((n−1)!)\varphi((n - 1)!) 递推过来。
注意到 n!n! 有一个性质，就是其为所有不大于 nn 的质数的倍数。也就是说 φ(n!)\varphi(n!) 可以写成：
∏p∈P,p∣nφ(pk)\displaystyle \prod_{p \in \mathbb{P},p \mid n} \varphi(p^k)
其中所有的 k≥1k \ge 1，分类讨论一下：
当 n∈Pn \in \mathbb{P} 时，φ(n!)=φ((n−1)!)×(n−1)\varphi(n!) = \varphi((n - 1)!) \times (n − 1)。
当 n∉Pn \not \in \mathbb{P} 时，φ(n!)=φ((n−1)!)×n\varphi(n!)=\varphi((n - 1)!) \times n。
于是可以递推得到 φ(n!)\varphi(n!)。

细节

预处理后，除法用逆元处理即可，提交以后，恭喜你，炸了。
因为题目中并没有说明 r>mr \gt m，所以逆元可能会爆炸！
所以，在预处理时，我们要将所有数写成 a×rb(r∤a)a \times r^b(r \nmid a) 的形式，用两个数组分别存储 aa 和 bb。
当两数相乘时将 aa 相乘，将 bb 相加，当两数相除时用除数的 aa 乘上倍数数 aa 的逆元，将 bb 相减即可。
最后，如果答案的 b>0b \gt 0 那么答案  mod r \bmod r 的结果即为 00，输出 00 即可。
反之，如果答案的 b=0b = 0，则输出答案的 aa 即可。

代码

CPP
#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;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...