【BZOJ2186】【SDOI2008】沙拉公主的困惑

要求\(n!\)范围内与\(m!\)互质的数的个数

根据欧几里得boy的定理,\((x,m!)=1\)意味着\((x\bmod m!,m!)=1\)

也就是说只要求出\(\varphi(m!)\)再乘上\(\frac{n!}{m!}\)

阶乘及其逆元都是可以\(O(n)\)求出的

根据定义,\(\varphi(m!)=m!\prod(p-1)p^{-1}\),其中\(p\)为不大于\(m\)的质数

预处理前缀积,二分即可。

说点什么

  Subscribe  
提醒