题目描述
给定 nn 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 \(ai×xi≡bi(\%mi)\)，如果无解则输出
impossible。输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组数据 ai,bi,mi
输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi，如果无解则输出
impossible。每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 int范围之内。
数据范围
1≤n≤105
1≤ai,bi,mi≤2×1091输入样例：
2 2 3 6 4 3 5输出样例：
impossible -3
扩展欧几里得算法求解
分析
因为 $a∗x≡b(% m) $等价于 \(a∗x−b\) 是m的倍数，因此线性同余方程等价为 \(a∗x+m∗y=b\)
根据 Bezout 定理，上述等式有解当且仅当 \(gcd(a,m)|b\) （\(b整除 gcd(a,m)\)）
因此先用扩展欧几里得算法求出一组整数 \(x0,y0\) 使得 \(a∗x0+m∗y0=gcd(a,m)\)。 然后$ x=x0∗b/gcd(a,m)%m$ 即是所求。
代码
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long LL;
// 返回 gcd(a,b)
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;
scanf("%d", &n);
while(n --)
{
int a, b, m;
scanf("%d%d%d", &a, &b, &m);
int x, y;
int d = exgcd(a, m, x, y);
if(b % d) // b不能整除gcd(a,b)，此时无解
{
printf("impossible\n");
}
else
{
LL res = (LL) x * b / d % m;
printf("%lld\n", res);
}
}
return 0;
}