Solution - P2155 [SDOI2008] 沙拉公主的困惑

P2155 [SDOI2008] 沙拉公主的困惑

idea:

推式子，转化为欧拉函数

解决方案：

根据题意写式子：

$$\sum_{i=1}^{n!} [gcd(i,m!)=1]\ \ \ \$$

$$=\sum_{i=1}^{n!} [gcd(i\%m!,m!)=1]$$

$$=\frac{n!}{m!}\sum_{i=1}^{m!}[gcd(i,m!)=1]\ \$$

$$=\frac{n!}{m!}\varphi(m!)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

$$=\frac{n!}{m!}\prod_{p^k\mid m!,p\in\mathbb{P}} p^k(1-\frac{1}{p})\ \ \$$

$$=n!\prod_{p|m!,p\in\mathbb{P}} \frac{p-1}{p}\ \ \ \ \ \ \ \ \ \ \ \ \ \$$

这个式子就可以处理了。需要注意的是， $R$ 可能会很小，这时要上下同时约去 $R$ 。