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

Isprime · 2021-08-27 17:34:58 · 题解

题意简述：给定 N,M,R，求 [1,N!] 中与 M! 互质的数的数量。

伟大的欧几里得已经告诉我们该怎么做了。

题目中限定了 M \leq N，那么显然 M! | N!.

常识告诉我们，gcd(a,b)=gcd(a+k\times b,b).然而常识很多时候是假的，所以我们考虑证明这个式子。

设 s=gcd(a,b), 则存在 x,y\in\mathbb{Z}使得 a=x\times s,b=y\times s,gcd(x,y)=1，于是 gcd(a+b\times k,b)=gcd(x\times s+y\times s\times k,y\times s)=gcd(s\times(x+y\times k),s\times y)=s\times gcd(x+y\times k,y).

设 m|(x+y\times k) 且 m|y，所以 m|(y\times k)，所以 m|x.即 m|x 且 m|y，又因为 gcd(x,y)=1，所以 gcd(x+y\times k,y)=m=1，所以 gcd(a+b\times k,b)=s\times gcd(x+y\times k,y)=s=gcd(a,b).

这个式子能说明什么呢？我们令 b=M!,显然可以发现：对于 \forall k\in [1,\frac{N!}{M!}],\forall x\in[1,M!] 有 gcd(k*M!+x,M!)=gcd(x,M!).

也就是说，对于 \forall k\in [1,\frac{N!}{M!}], [(k-1)\times M!+1,k\times M!] 中与 M! 互质的数是相等的。

得出这个结论之后就简单了。答案就是 \frac{N!}{M!}\times \phi(M!).