求逆元

拓展欧几里得

求a的在模n下的逆元，实际上就是求一个整数x，使得

ax = 1 (mod n)

于是我们通过拓展gcd解方程来求解

ax + ny = gcd(a,n)

在如上方程中，只有满足以下才存在逆元

gcd(a,n) = 1

则

(ax + ny) % n = ax % n = 1 % n = 1

即

ax = 1 (mod n)

代码如下：

//get integer x and y, making ax + by = d and minimise |x| + |y|. for d = gcd(a,b) //though a and b are integers, x and y still may be lager than max_integer void exgcd(long long a, long long b, long long &d, long long &x, long long &y) { if (!b) { d = a; x = 1; y = 0; } else { exgcd(b, a % b, d, y, x); y -= x * (a / b); } } //get inverse element of a in condition of mod n //return -1 means doesn't existed long long inv(long long a, long long n) { long long d, x, y; exgcd(a, n, d, x, y); return d == 1 ? (x + n) % n : -1; }

欧拉定理

求a在模n下的逆元，当n为一个质数时，根据欧拉定理

x = n ** (phi(n) - 1)

phi(n) = n - 1

上式中phi(n)为n的欧拉函数，且假设n为质数

代码如下：

#include <iostream> using namespace std; //get (a ** p) % mod long long pow_mod(long long a, long long p, long long mod) { if (p == 0) return 1; long long ans = pow_mod(a, p / 2, mod); ans = (ans * ans) % mod; if (p % 2) ans = (ans * a) % mod; return ans; } int main() { long long a = 233, mod = 1000000007; long long inv = pow_mod(a, mod - 2, mod); //'inv' is the answer we get return 0; }

转载于:https://www.cnblogs.com/ScratchingBear/p/5540704.html

相关资源：求逆元程序