线性同余方程

题目描述

给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 ai×xi≡bi(modmi)，如果无解则输出 impossible。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组数据 ai,bi,mi。
输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi
，如果无解则输出 impossible。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 int 范围之内。
数据范围
1≤n≤105,1≤ai,bi,mi≤2×109
输入样例：
2
2 3 6
4 3 5
输出样例：
impossible
-3

 变形为拓展欧几里得形式：a * x + b * y = gcd(a, b)
 原式变为：   a * x = m * y + b  (注：mod m 为 b, 则相当于结果为 m 的倍数和 b 的和)
              a * x - m * y = b
 另y1 = -y得：a * x + m * y1 = b
 根据拓展欧几里得定理，只要 b 是 gcd(a, m)的倍数即有解！
 另d = gcd(a, m), 我们得到的式子其实是：a * x + m * y1 = gcd(a, m) = d (注；上面的b其实就是d的倍数)
 所以左右同乘 b / d 即可转化为：a * x * b / d + m * y1 * b / d = b * b / d = b
 即最后答案为：res = x * d / b % m

代码

#include <bits/stdc++.h>
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;
}
int main(){
    int n;
    cin >> n;
    while(n --){
        int a,b,m,x,y;
        cin >> a >> b >> m;
        int d = exgcd(a,m,x,y);
        if(b % d) puts("impossible");
        else cout << x * 1ll * b / d % m << endl;
    }
    return 0;
}