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

这题思路其实并不难,但是很坑。我们可以回想一下我们是如何证明求欧拉函数$\varphi$的公式的。我们将m!分解质因数结果中的质数记为$p_1,p_2,p_3,…p_k$,即当且仅当一个数的质因子中至少有这k个质数中的其中一个,那么这个数就不和m!互质,不难发现,这k个数刚好是1~m中的质数.我们用这k个质数到1~n!中去用一个容斥原理之后再因式分解,就可以得到我们需要的答案为:
$n!\prod\displaystyle_{i=1}^k(p_i-1)/p_i$
然后由于数据规模比较大,我们需要一个线性求逆元的方法:$inv[i]=(p-p/i)inv[p\%i] $
(证明自行百度)
这题还有好多坑,比如内存比较小,开longlong数组会爆炸,我们要在运算时把数据转成longlong,算完再转成int.以及时间比较卡需要一点常数优化.
代码:

Tagged with:

发表评论