题目描述

线性同余方程
给定 $a,b,m $，求x使得 $ a*x\equiv b(\bmod m)$
上式等价于 $ ax = y*m + b$ 其中y为任意整数,进一步等价于
$ x*a + {y}’*m = b$ 其中${y}’=-y$
此时，求解a和m的最大公约数g和线性表出最大公约数的系数$k_{1}$ 和 $k_{2}$（$ k_{1}*a+k_{2}*m == (a,m)$）
根据裴属定理知，两个数的线性和一定为两数最大公约数的倍数。
所以，当b为g的倍数时才有解，解得 $x = b/g*k_{1} \bmod m $（模m是因为x的解有很多，我们喜欢最小的一个解）

样例

#include <iostream>
#include <cstring>
#include <algorithm>
typedef long long LL;

using namespace std;

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

int main()
{
    int N;
    int a,b,m;
    int x,y;
    int g;
    cin>>N;


    while(N--){
        cin>>a>>b>>m;
        g=exgcd(a,m,x,y);
        if(b%g!=0) cout<<"impossible\n";
        else printf("%d\n",(LL)b/g*x%m);

    }
}