c++ 1~p-1的逆元

如果p是一个质数，那么可以使用费马小定理求解1~p-1的逆元。费马小定理是指如果p是一个质数，a是一个整数，那么a^(p-1) mod p = 1。因此，对于a，a^(p-2) mod p就是a的逆元。

以下是使用费马小定理求解1~p-1的逆元的C++代码：

#include <iostream>
using namespace std;

int pow(int a, int b, int p) {
    int ans = 1 % p;
    for (; b; b >>= 1) {
        if (b & 1) ans = ans * a % p;
        a = a * a % p;
    }
    return ans;
}

int inv(int a, int p) {
    return pow(a, p - 2, p);
}

int main() {
    int p = 1000000007;
    for (int i = 1; i < p; ++i) {
        cout << i << " 的逆元是 " << inv(i, p) << endl;
    }
    return 0;
}

在这个例子中，我们使用了快速幂来计算a的乘方，然后将其除以p并取模。我们使用inv函数来计算a的逆元，该函数使用费马小定理计算a^(p-2) mod p。在主函数中，我们循环计算1~p-1的逆元，其中p是一个质数。

相关问题

编写一个函数 int inverse(int p, int a)，输入模 p 乘法群 Zp*={1, 2, 3, …, p-1}中的 任何元素 a，实现扩展欧几里得定理，函数能够输出 a 的乘法逆元。

编写一个名为 `inverse` 的函数，用于计算给定整数 `a` 在模 `p` 下的乘法逆元，可以遵循以下步骤，利用扩展欧几里得算法。这个算法不仅找到两个数的最大公约数，还返回它们的贝祖等式解，即 `(x, y)` 满足 `ax + py = gcd(a, p) = 1`。

// C++ 代码实现

#include <iostream>
using namespace std;

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

// 扩展欧几里得算法求逆元
pair<int, int> extendedEuclidean(int a, int p) {
    // 初始化 x, y 和 r
    int x = 0, y = 1, r = a; // r 相当于 a
    while (r != 0) {
        int q = p / r;
        pair<int, int> temp(x, y); // 保存中间结果
        x -= q * r;   // 更新 x
        y -= q * r;   // 更新 y
        r = p % r;    // 更新 r，相当于 p = r
        p = r;       // 更新原值为新的 r
    }
    return make_pair(x, y); // 返回逆元和 GCD
}

// 函数 inverse 实现
int inverse(int p, int a) {
    auto result = extendedEuclidean(a, p);
    if (result.first == 1) { // 如果 GCD 等于 1，则 x 是 a 的逆元
        return result.second % p;
    } else {
        throw runtime_error("a is not invertible modulo p"); // 如果 a 无逆元，抛出异常
    }
}

int main() {
    try {
        int p, a;
        cout << "Enter modulus p and element a: ";
        cin >> p >> a;
        int inv = inverse(p, a);
        cout << "The multiplicative inverse of " << a << " modulo " << p << " is: " << inv << endl;
    } catch (const exception& e) {
        cerr << "Error: " << e.what() << endl;
    }
    return 0;
}

在这个函数中，用户需要输入 `p` 和 `a`，然后程序会计算并输出 `a` 在模 `p` 下的逆元。如果 `a` 不能在 `Z_p*` 中找到逆元（如 `gcd(a, p) ≠ 1`），则函数将抛出异常。

辗转相除法求模乘逆元的c++代码

辗转相除法求模乘逆元的 C 代码如下：

#include <stdio.h>
int extgcd(int a, int b, int &x, int &y)
{
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}
int mod_inverse(int a, int m)
{
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}
int main()
{
    int a = 3, m = 11;
    printf("%d 的模 %d 乘逆元为 %d\n", a, m, mod_inverse(a, m));
    return 0;
}

以上代码使用了扩展欧几里得算法求解模乘逆元。其中，`extgcd` 函数可以求解任意两个整数的最大公约数，并返回其值，同时通过引用返回参数 `x` 和 `y` 的值，满足 $ax + by = \gcd(a, b)$。`mod_inverse` 函数则使用 `extgcd` 求解模乘逆元，即 $a$ 模 $m$ 的乘法逆元 $x$，满足 $ax \equiv 1 \pmod m$，并返回其值。