AcWing 878. 线性同余方程
原题链接
简单
作者:
我要出去乱说
,
2021-01-20 23:15:09
,
所有人可见
,
阅读 319
#include <iostream>
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;
while (n -- )
{
int a, b, m;
cin >> a >> b >> m;
int x, y;
int d = exgcd(a, m, x, y); //用扩展欧几里得算法求出a与m的最大公约数d
if (b % d) puts("impossible"); //成立条件:(a, m) | b, b必须能够整除a和m的最大公约数d
else printf("%d\n", (LL)x * (b / d) % m);
}
return 0;
}