扩展欧几里得算法求逆元c++c++
时间: 2023-07-23 18:05:00 浏览: 63
欧几里得算法可以用来求解两个数的最大公约数,而扩展欧几里得算法则可以在求解最大公约数的同时,找到使得两个数的线性组合等于最大公约数的系数。下面是用C++实现的扩展欧几里得算法来求逆元的示例代码:
```cpp
#include <iostream>
using namespace std;
int extendedEuclidean(int a, int b, int& x, int& y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int gcd = extendedEuclidean(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return gcd;
}
int inverseModulo(int a, int m) {
int x, y;
int gcd = extendedEuclidean(a, m, x, y);
if (gcd != 1) {
throw "Inverse does not exist.";
}
return (x % m + m) % m;
}
int main() {
int a, m;
cout << "Enter the number and modulo: ";
cin >> a >> m;
try {
int inv = inverseModulo(a, m);
cout << "The inverse of " << a << " modulo " << m << " is: " << inv << endl;
} catch(const char* msg) {
cerr << msg << endl;
}
return 0;
}
```
这段代码通过扩展欧几里得算法求解了给定数的逆元,并进行了异常处理,以确保逆元存在。用户可以输入一个数和一个模数,程序将输出给定数的逆元。