C++ 代码

#include<iostream>
#include<cstdio>
#include<cmath>

using namespace std;
long long gcd(long long a,long long b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)//扩展欧几里得算法
{
    if(b==0)
    {
        x=1;y=0;
        return a;  //到达递归边界开始向上一层返回
    }
    long long r=exgcd(b,a%b,x,y);
    long long temp=x;
    x=y;    //把x y变成上一层的
    y=temp-(a/b)*y;
    return r;     //得到a b的最大公因数
}
int main()
{
    long long a,b,x,y,r,m,k,t;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>m;
        if(b%gcd(a,m)==0)
        {
            r=exgcd(a,m,x,y);
            cout<<(((b*x)/r)%(m/r)+m/r)%(m/r)<<endl;
        }
        else
            cout<<"impossible"<<endl;
    }
    return 0;
}