钾肥喵的窝

我在 CODING 部署的 Hexo 博客

0%

题解 【P5091】 【模板】扩展欧拉定理

题面

https://www.luogu.com.cn/problem/P5091

基本思路

(根据题解可知)这题用欧拉降幂+快速幂解决.

下面开始介绍
温馨提示: 为了您的阅读体验, 请坐和放宽, 等待图片加载完成

扩展欧拉定理

公式如下, 证明请自行查阅资料:

公式在膜m意义下成立(才不会说是我打LaTeX的时候忘记加了 已经加上了)

套用上面的公式, 我们现在只需要求出欧拉函数的值即可

欧拉函数

定义见各大百科, 下面推导一个式子用于编程:

首先是欧拉函数的两个性质(下面的p是一个质数):

我们很容易推导出下面的式子:

代码正确性

首先我们根据数论知识可以知道, 判断质数时只要试到 √n 即可.
当试出一个因子时, 我们用一个循环尝试继续提取这个因子, 因此, 每试出一个因子, n的唯一分解式就减少了一项(也就是减少了一个 pmkm ).
因为我们是从小到大尝试的, 所以必然不会试出合数因子(拆分成更小的质数在之前的循环中被剥离了).
这里有个问题, 如果 n 是质数, 不会引起ans的变化, 因此, 循环结束后需要特判.

快速幂

详见传送门:
P1226 【模板】快速幂||取余运算

完整AC代码