13.线性同余方程 扩展欧几里得算法

 

 扩展欧几里德算法的简单应用，就是求解线性同余方程

先把这个等式做变形

 只要保证b能整除a和m的最大公约数，即b是a和m最大公约数的倍数

 就有解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) {
        x = 1;
        y = 0;
        //x = 1， y = 0是一组解
        return a;
    }
    ll d = exgcd(b, a % b, y, x); //翻转一下
    y -= a / b * x;
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    while (n--) {
        ll a, b, m;
        cin >> a >> b >> m;
        ll x, y;
        ll d = exgcd(a, m, x, y);
        if (b % d) {
            cout << "impossible" << endl;
        } else {
            cout << x * (b / d) % m << endl;
        }
    }
    return 0;
}