/原理：
若：(ax) % m= b, 那么一定存在y使得: ax - my = b,
令 y1 = -y –> ax + y1m = b
对比扩展欧几里得公式：ax + by = gcd(a,b) 得出当b是gcd(a,m)的倍数时才x,y1才有解
*/

C++ 代码

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

int exgcd(int a, int b, int &x, int &y)
{
    if(!b)
    {
        x = 1, y = 0;
        return a;
    }
    //最终d=gcd（a，b）
    int d = exgcd(b, a%b, y, x);
    y -= a/b*x;
    return d; 
}



int main()
{

    int n, x, y;
    cin >> n;
    while(n--)
    {
        int a, b, m;
        cin >> a >> b >> m;
        int d = exgcd(a, m, x, y);
        if(b%d==0)
            cout << (long long)b/d*x%m << endl;
        else
            puts("impossible");
    }

    return 0;
}