一次同余方程求解c++

在C++中，可以使用扩展欧几里得算法和取模运算来求解一次同余方程。以下是一个实现示例：

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int extend_gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extend_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

int mod_inverse(int a, int m) {
    int x, y;
    extend_gcd(a, m, x, y);
    return (x % m + m) % m;
}

int solve_congruence(int a, int b, int m) {
    if (gcd(a, m) != 1) {
        return -1; // 无解
    }
    return (b * mod_inverse(a, m)) % m;
}

int main() {
    int a = 3, b = 2, m = 5;
    int x = solve_congruence(a, b, m);
    if (x == -1) {
        cout << "No solution" << endl;
    } else {
        cout << "x = " << x << endl; // 输出 x = 4
    }
    return 0;
}

其中，“gcd”函数用于计算最大公约数，“extend_gcd”函数用于计算扩展欧几里得算法和贝祖等式ax + by = d 的解，“mod_inverse”函数用于计算a模m的逆元。

“solve_congruence”函数实现了一次同余方程的求解。如果a和m不互质，则无解，返回-1。否则，计算a模m的逆元，然后使用取模运算得到解。

最后在主函数中输入方程的系数和模数，调用solve_congruence函数求解一次同余方程，并输出结果。