辗转相除法求模乘逆元的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$，并返回其值。

相关问题

用c++写一个用辗转相除法求任意数的模乘逆元的代码

以下是用辗转相除法求任意数的模乘逆元的C代码：

#include <stdio.h>

int extended_gcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }

    int r = extended_gcd(b, a % b, y, x);
    *y -= (a / b) * (*x);

    return r;
}

int mod_inverse(int a, int m) {
    int x, y;
    int gcd = extended_gcd(a, m, &x, &y);

    if (gcd != 1) {
        printf("The inverse of %d does not exist modulo %d.\n", a, m);
        return -1;
    } else {
        return (x % m + m) % m;
    }
}

int main() {
    int a, m;
    printf("Enter a and m (separated by a space): ");
    scanf("%d %d", &a, &m);

    int inv = mod_inverse(a, m);
    if (inv != -1) {
        printf("The inverse of %d modulo %d is %d.\n", a, m, inv);
    }

    return 0;
}

该程序中的 `extended_gcd` 函数实现了扩展欧几里得算法，用于计算最大公约数和模乘逆元。 `mod_inverse` 函数则利用 `extended_gcd` 函数求出模乘逆元（如果存在）并返回。在主函数中，程序要求用户输入要求模乘逆元的数和模数，并输出计算结果。

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作为提示。