莫欺少年穷，修仙之旅在这开始—>算法基础课题解

线性同余方程： $ax\equiv b\pmod{m}$

前提： $\gcd(a,m)\mid b$

推导过程： 存在 $y’$，使得 $ax=my’+b$，令 $y=-y’$，则 $ax+my=b$

扩展欧几里得算法可求： $ax_0+my_0=\gcd(a,m)$

结论： $x=x_0 \cdot \dfrac{b}{\gcd(a,m)}$

可参考： 扩展欧几里得算法

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

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;

    int a,b,m,x,y;
    while(n--)
    {
        cin>>a>>b>>m;

        int d=exgcd(a,m,x,y);
        if(b%d) cout<<"impossible"<<endl;
        else cout<<(LL)x*b/d%m<<endl;
    }

    return 0;
}