线性同余方程

​ 给定 $a,b,p$ ，求出 $x$ 使其满足
$$ a·x\equiv b\mod p $$
​ 这个方程可以写为
$$ ax+py=b $$
​ 要使该方程有解，则满足
$$ b=k·(a,p),k\in Z $$
​

​ 用扩展欧几里得算法求出 $ax+py=(a,p)$ 的 $x$ 的解之后，再将 $x$ 乘上 $\frac{b}{(a,p)}$即可。

代码

void solve(int a, int b, int p){
    int x, y;
    int d = exgcd(a, p, x, y);
    if (b % d)  cout << "impossible"; 
    else
        cout << x * b / d % p;
}

完整代码

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

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

void solve(int a, int b, int p){
    int x, y;
    int d = exgcd(a, p, x, y);
    if (b % d)  cout << "impossible"; 
    else
        cout << x * b / d % p;
    cout << endl;
}

main(){
    int t;
    cin >> t;
    while (t -- ){
        int a, b, p;
        cin >> a >> b >> p;
        solve(a, b, p);
    }

    return 0;
}