BZOJ 2186 [Sdoi2008] 沙拉公主的困惑

发布于 2017-04-12  216 次阅读


题目地址:http://www.lydsy.com/JudgeOnline/problem.php?id=2186


题意:T 组询问,对于每组询问,给出一个 n 和 m,求小于等于 n! 的正整数中,与 m! 互质的数有多少,给出一个确定的质数 R 对答案取模。

R≤109+10                   T≤105                   1≤m≤n≤107


们看到 T≤105, 知道一定不能暴力,需要预处理点什么东西。

首先有一个显然的结论,若 gcd(x,y)=1,则 gcd(x+y,y)=1. 下面给出简单的证明:

使用反证法,若 gcd(x+y,y)=K (K≥2),则有:x+y=PK,y=QK .

那么 x=PK-Y=(P-Q)K    y=QK 显然与 gcd(x,y)=1 矛盾,证毕。

我们考虑答案是怎样组成的,对于≤m! 的答案,显然是$$\varphi (m!) $$ 将这些满足条件的数按照上述结论倍增,所得到的数显然也符合,那么答案即是$$ans=\varphi (m!) \cdot \frac{n!}{m!}$$

由于 m! 恰好包括了从 2 到 m 的所有质数,所以 (p 为质数)$$\varphi (m!)=m!\prod_{p=2}^{m} \frac{p-1}{p}$$

那么 $$ans=n!\prod_{p=2}^{m}\frac{p-1}{p}$$

然后这个式子里,素数表,逆元,阶乘我们都可以预处理,问题就解决啦!

代码如下:(蒟蒻博主调智障错误 2h qwq

 


一个非常弱的准退役OIER