给定 𝑛 组数据 𝑎𝑖,𝑏𝑖,𝑚𝑖，对于每组数求出一个 𝑥𝑖，使其满足 𝑎𝑖×𝑥𝑖 ≡ 𝑏𝑖(mod𝑚𝑖)，如果无解则输出 impossible。

输入格式

第一行包含整数 𝑛。

接下来 𝑛 行，每行包含一组数据 𝑎𝑖,𝑏𝑖,𝑚𝑖。

输出格式

输出共 𝑛 行，每组数据输出一个整数表示一个满足条件的 𝑥𝑖，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 𝑖𝑛𝑡 范围之内。

数据范围

1≤n≤,
1≤𝑎𝑖,𝑏𝑖,𝑚𝑖≤2×

输入样例：

2
2 3 6
4 3 5

输出样例：

impossible
-3

代码：
 

#include<iostream>
using namespace std;int n;int EXT_gcd(int a,int b,int &x,int &y){if(b == 0){x = 1;y = 0;return a;}else{int d = EXT_gcd(b,a % b,x,y);int temp = y;y = x - (a/b) * y;x = temp;return d;}
}int main(){cin>>n;while(n--){int a,b,m,x,y;cin>>a>>b>>m;int res = EXT_gcd(a,m,x,y);if(b % res != 0){cout<<"impossible"<<endl;}else{cout<<(long long)x * (b / res) % m<<endl;}}return 0;
}