如何算a^ mod 1000000007逆元（int范围以内），c++函数

计算 a 的模 1000000007 的逆元通常涉及到欧几里得算法以及扩展欧几里得算法。下面是一个简单的 C++ 函数示例，用于求解整数 a 对于模 m=1000000007 的乘法逆元：

#include <extgcd.h>

// 使用gmp库中的函数计算最大公约数及其逆元
typedef std::pair<int, int> Pair;

// 求解ax ≡ 1 (mod m) 的逆元 x
int modular_inverse(int a, int m = 1000000007) {
    Pair result = extgcd(a, m); // extgcd 返回两个值：最大公约数和逆元
    if (result.first == 1) { // 如果最大公约数是1，说明存在逆元
        return static_cast<int>(result.second % m);
    } else {
        throw std::runtime_error("a is not invertible modulo m"); // a 和 m 互质才会有逆元，这里表示a无逆元
    }
}

// 使用方法
int main() {
    try {
        int a = ...; // 要查找逆元的数
        int x = modular_inverse(a);
        std::cout << "Modular inverse of " << a << " is " << x << std::endl;
    } catch (const std::exception& e) {
        std::cerr << "Error: " << e.what() << std::endl;
    }
    return 0;
}

这个函数首先使用 `extgcd` 函数来计算 a 和 m 的最大公约数，如果最大公约数为 1，则返回 a 的逆元；否则抛出异常，因为非互质的情况下没有逆元。