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

在计算整数 `a` 对于模数 `1000000007` 的逆元时，我们通常需要找到一个小于等于 `1000000007 - 1` 的整数 `x`，使得 `(a * x) % 1000000007 = 1`。这是因为 `a` 的逆元就是 `x`，如果它们满足这个条件。这种方法可以使用扩展欧几里得算法或者带余乘法来寻找。

以下是C++代码示例：

#include <bits/stdc++.h>
using namespace std;

// 求最大公约数
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

// 扩展欧几里得算法求逆元
pair<int, int> extendedEuclidean(int a, int m) {
    if (gcd(a, m) != 1) {
        cout << "Inverse does not exist!\n";
        return {0, 0};
    }
    
    int x = 0, y = 1, u = 1, v = 0;
    while (a != 0) {
        int q = m / a;
        int t = m - q * a;
        m = a; a = t;
        t = x; x = u - q * x;
        u = t;
        t = y; y = v - q * y;
        v = t;
    }
    return make_pair(x, m);
}

int modularInverse(int a, int m) {
    auto result = extendedEuclidean(a, m);
    // 如果存在逆元，则返回结果的第一个元素，因为它是x
    if (result.first > 0)
        return (result.first + m) % m; // 注意加上m确保在有效范围内
    else
        return (result.first - m) % m; // 若结果小于0，在范围内加上m
}

int main() {
    int a = ...; // 输入的整数
    int mod = 1000000007;
    int inv = modularInverse(a, mod);
    cout << "The inverse of " << a << " modulo " << mod << " is " << inv << endl;
    return 0;
}

在这个代码中，`modularInverse` 函数首先通过 `extendedEuclidean` 函数获取 `a` 和 `1000000007` 的最大公约数以及相应的逆元。然后将逆元调整到 `0` 到 `m-1` 范围内。注意，这里假设输入的 `a` 和 `1000000007` 互质，如果不互质则找不到逆元。