/*
C语言计bai算负数取余:符号内的被除du数决定,就zhi是计算式中的-7,7,-7决定:比dao如-7%5=-2;
7%-5=2;
-7%-5=-2;
负数zhuan取余shu的原理:
任何一个整数n都可以表示成n=kq+r其中0<=|r|<|q|这里的r就是n除以q的余数,即r==n%q例如:-9=(-2)4+(-1)则-9除以4的余数为-1。
求余:取整除后的余数。
求模:基本意义和求余相同,不过要求a%b中的b不是负数。
*/
include[HTML_REMOVED]
using namespace std;
typedef long long LL;
int x,y;
int exgcd(int a,int b,int &x,int &y)
{
if(!b)
{
x=1,y=0;
return a;
}
int d,x1,y1;
d=exgcd(b,a%b,x1,y1);
x=y1,y=x1-a/b*y1;
return d;
}
int main()
{
int n;
cin>>n;
while(n–)
{
int a,b,m;
scanf(“%d%d%d”,&a,&b,&m);
int d=exgcd(a,m,x,y);
//如果有解的话,b应该是d的整数倍
//同理,输出的x也应变成相应倍数
if(b%d) puts(“impossible”);//这是裴蜀定理
else{
x=(LL)x*b/d%m;
printf(“%d\n”,x);
}
}
return 0;
}