[BZOJ2186] [SDOI2008] 沙拉公主的困惑

题目

题目链接,题目要求求出 [1, n!] 中与 {m!} 互质的数的个数,结果模质数 R,其中 m < n.  

解题思路

首先有一点,[1, m!] 中与 \(m\) 互质的数的个数我们是会求的,即是 \phi(m!).那么大于 \(m\) 的怎么求呢?
我们知道,所有数的可以表示成 x*m! + y, 有欧几里得辗转相除 gcd(x*m! + y, m!) = gcd(y, m!), 所以 [1, m!] 中与 \(m\) 互质的数的个数 与 [km! + 1, (k+1)m!] 中与 {m!} 互质的数的个数 是相等的。而 n > m 所以[1, n!] 中与 {m!} 互质的数的个数为 \phi(m!) * n! / {m!}.
m! = p_1^{k_1} p_2^{k_2} ... p_x^{k_x}\phi(m!) = m! * \frac{(p_1-1)}{p_1} \frac{(p_2-1)}{p_2}...\frac{(p_x-1)}{p_x} 那么 \phi(m!) * n! / m! = \frac{(p_1-1)}{p_1} \frac{(p_2-1)}{p_2}...\frac{(p_x-1)}{p_x} * {n!}
所以,可以用线性筛预处理出素数,用递推法预处理出所有数的逆元,两者结合可以线性预处理出 \phi(m!)  / {m!}, 接着预处理出阶乘。最后遇到查询直接 O(1) 计算即可。
 

代码

 

完结

依旧参考黄学长博客
这几天高产似母猪😌😌😌😌😌😌😌

发表评论

电子邮件地址不会被公开。 必填项已用*标注