推导过程

• $ax \equiv b(mod\;m)$就可以推出$ax =my+b$
• 变形一下$ax-my =b$,不就是系数为a和-m的扩欧算法吗,即exgcd(a,-m,x,y)
• 怎么判断有没有解呢,根据裴蜀定理ax+my所能构造的最小正整数就是gcd(a,m),即$ax+my=gcd(a,m)$
• 那么要有解的情况下,b必须是gcd(a,m)的倍数,即$b\%gcd(a,m)=0$
• 由于exgcd(a,m,x,y)求得的x只是ax+my=gcd(a,m)的解
• 要求得ax+my=b的解,直接将x乘以b/gcd(a,m)的倍数即可,即$x^{\prime}=x\times \frac{b}{gcd(a,m)}$
• 最后一定要转换为longlong,防止爆int,并且要转换到int范围里，取余m即可

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;

int n;

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

int main()
{
    cin>>n;
    while (n -- )
    {
        int a,b,m,x,y;
        cin>>a>>b>>m;
        int d=exgcd(a,-m,x,y);//这里求出来的x只是ax+my=gcd(a,m)的x,要求得ax+my=b;方程两边都扩大b/gcd(a,m)倍
        if(b%d!=0) cout<<"impossible"<<endl;
        else cout<<(LL)x*(b/d)%m<<endl;//放在m的解系中
    }

}