计算模n加法的逆元C++

计算模n加法的逆元是指在一个模意义下找到一个数x，使得(x * y) % n = 1，其中y是给定的原数。在C++中，如果y不是n的倍数，那么它在模n下的逆元是存在的，并且可以通过扩展欧几里得算法或费马小定理找到。

以下是一个简单的例子，展示如何使用扩展欧几里得算法求解两个数a和n（n为素数）之间的逆元：

#include <iostream>
#include <vector>

// 定义扩展欧几里得函数
std::pair<int, int> extendedEuclidean(int a, int m) {
    if (m == 0) return {1, 0}; // 当m=0时，直接返回1和0作为结果
    std::pair<int, int> x_y = extendedEuclidean(m, a % m);
    int x = x_y.first;
    int y = x_y.second;
    return {y, x - (a / m) * y};
}

// 求逆元
int modularInverse(int a, int n) {
    auto result = extendedEuclidean(a, n);
    return (result.first + n) % n; // 为了得到正确的负整数范围内的结果
}

int main() {
    int a, n;
    std::cout << "Enter a number (a): ";
    std::cin >> a;
    std::cout << "Enter modulus (n): ";
    std::cin >> n;

    if (gcd(a, n) != 1) {
        std::cout << "Numbers are not coprime. Inverse does not exist." << std::endl;
        return 0;
    }

    int inv_a = modularInverse(a, n);
    std::cout << "The inverse of " << a << " modulo " << n << " is: " << inv_a << std::endl;

    return 0;
}

// 函数gcd用于计算最大公约数，这里省略了实现

在这个示例中，`modularInverse`函数首先通过`extendedEuclidean`计算a和n的最大公约数（gcd），然后根据扩展欧几里得的结果计算出逆元。如果a和n互质（即gcd(a, n)=1），则有逆元存在，否则没有逆元。