hiho一下第279周《分数取模》题目分析

1
0

《分数取模》题目分析

这道题本质上就是求b关于模p的逆元b^-1。

求逆元有多种方法,如果p是质数,根据费马小定理,b^(p-1) ≡ 1 mod p,即b * b^(p-2) ≡ 1 mod p,所以 b^(p-2) 就是b的逆元。

计算b^(p-2)使用快速幂即可。

不过本题并没有说p一定是质数,而只说b与p互质。

这种情况下,有欧拉定理:b^φ(p) ≡ 1 mod p,其中φ(p)是欧拉函数,详情可见数论五·欧拉函数。所以有b^(φ(p)-1)就是b的逆元。 φ(p)可以通过O(sqrt(p))暴力求出,然后利用快速幂计算b^(φ(p)-1)即可。

还有一种方法是用扩展欧几里德求解 bx + kp = 1,x即是b的逆元。扩展欧几里德算法可参考数论四·扩展欧几里德

0 answer(s)

write answer 切换为英文 切换为中文


转发分享