euclid算法c++求乘法逆元

欧几里得算法（Euclidean Algorithm），也称为辗转相除法，用于计算两个正整数的最大公约数（GCD）。在寻找乘法逆元时，如果我们要找到一个数a对于模m的逆元b，使得a * b ≡ 1 (mod m)，那么可以利用这个算法辅助计算。以下是C++中使用欧几里得算法求解乘法逆元的一个简化版本：

#include <iostream>
using namespace std;

// GCD function using Euclidean algorithm
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// Modular multiplicative inverse function
int modInverse(int a, int m) {
    // 根据扩展欧几里得算法
    int x = 0, y = 1, g = gcd(a, m);
    if (g != 1) {
        cout << " modular inverse does not exist";
        return -1; // 如果a和m互质，则无逆元
    }

    while (g != m) {
        int q = m / g;
        int temp = x;
        x = y - q * x;
        y = temp;
        g = g % m;
    }
    return (x + m) % m; // 为了得到模内的值
}

int main() {
    int a, m;
    cout << "Enter the number and modulus: ";
    cin >> a >> m;

    int inv = modInverse(a, m);
    if (inv != -1)
        cout << "The modular inverse of " << a << " modulo " << m << " is: " << inv << endl;
    else
        cout << "Modular inverse does not exist for this pair." << endl;

    return 0;
}

在这个程序中，`gcd()`函数用于计算a和m的最大公约数，然后`modInverse()`函数通过扩展欧几里得算法找出a关于模m的逆元。如果无法找到逆元（即a和m互质），则返回-1作为提示。