《分数取模》题目分析
这道题本质上就是求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的逆元。扩展欧几里德算法可参考数论四·扩展欧几里德。