乘法逆元的计算方法

• langzi291 发布于
• 1733 收藏

利用费马小定理 如果p为质数，gcd(a,p)=1，那么a^(p-1) ≡1 (mod p)  则a^(p-2) ≡1/a (mod p)  a^(p-2) ≡ inv(a) (mod p)  inv(a) = a^(p-2) (mod p)  其中时间复杂度为O(logn) 注意：模数 mod必须为质数才可以利用费马小定理求解 typedef long long ll; ll quick...