【题目来源】
AcWing：878. 线性同余方程 - AcWing题库
【题目描述】
给定 \(n\) 组数据 \(a_i,b_i,m_i\)，对于每组数求出一个 \(x_i\)，使其满足 \(a_i\times x_i \equiv b_i(mod\ m_i)\)，如果无解则输出 impossible。
【输入】
第一行包含整数 \(n\)。
接下来 \(n\) 行，每行包含一组数据 \(a_i,b_i,m_i\)。
【输出】
输出共 \(n\) 行，每组数据输出一个整数表示一个满足条件的 \(x_i\)，如果无解则输出 impossible。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 \(int\) 范围之内。
【输入样例】
2
2 3 6
4 3 5
【输出样例】
impossible
-3
【解题思路】
【算法标签】
《AcWing 878 线性同余方程》 #数学知识# #同余# #扩展欧几里得算法#
【代码详解】
#include <bits/stdc++.h>
using namespace std;long long x, y; // 定义全局变量 x 和 y，用于存储扩展欧几里得算法的解// 扩展欧几里得算法，用于求解 ax + by = gcd(a, b) 的一组整数解
int exgcd(int a, int b)
{if (b == 0) { // 如果 b 为 0，递归终止x = 1, y = 0; // 解为 x = 1, y = 0return a; // 返回 gcd(a, b)}int r = exgcd(b, a % b); // 递归求解long long x1 = x, y1 = y; // 保存递归结果// 更新 x 和 y 的值x = y1;y = x1 - a / b * y1;return r; // 返回 gcd(a, b)
}int main()
{int n; // 定义整数 n，表示查询的次数cin >> n; // 输入查询的次数while (n--) { // 遍历每个查询int a, b, m; // 定义整数 a, b, mcin >> a >> b >> m; // 输入 a, b, mint r = exgcd(a, m); // 使用扩展欧几里得算法求解 gcd(a, m)if (b % r > 0) // 如果 b 不能被 gcd(a, m) 整除cout << "impossible" << endl; // 输出 "impossible"else// 计算方程的解并输出cout << (long long)b / r * x % m << endl;}return 0; // 程序结束
}
【运行结果】
2
2 3 6
impossible
4 3 5
-3