AcWing 878. 线性同余方程
原题链接
简单
作者:
Drifter
,
2021-01-16 17:08:39
,
所有人可见
,
阅读 259
进阶 Day 2
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int ex_gcd(int a, int b, int &x, int &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
int d = ex_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
} //ex_gcd
int main(void)
{
int n;
scanf("%d", &n);
while (n--)
{
int a, b, m, x, y;
scanf("%d%d%d", &a, &b, &m);
int gcd = ex_gcd(a, m, x, y);
if(b % gcd == 0) printf("%d\n", (LL)x * b / gcd % m);
else puts("impossible");
}
return 0;
}