C++ 数论相关题目线性同余方程（扩展欧几里得算法的应用）

本文主要是介绍C++ 数论相关题目线性同余方程（扩展欧几里得算法的应用），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定 n
组数据 ai,bi,mi
，对于每组数求出一个 xi
，使其满足 ai×xi≡bi(modmi)
，如果无解则输出 impossible。

输入格式
第一行包含整数 n
。

接下来 n
行，每行包含一组数据 ai,bi,mi
。

输出格式
输出共 n
行，每组数据输出一个整数表示一个满足条件的 xi
，如果无解则输出 impossible。

每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。

输出答案必须在 int
范围之内。

数据范围
1≤n≤105
,
1≤ai,bi,mi≤2×109
输入样例：
2
2 3 6
4 3 5
输出样例：
impossible
-3
在这里插入图片描述
题目的等式等价于上述图片的最后一行，也就是：给定a、m、b，求系数x使得等式成立，就是就是扩展欧几里得算法，有解的充分必要条件就是b能整除a和m的最大公约数，否则一定无解。

#include <iostream>using namespace std;int n;int exgcd(int a, int b, int &x, int &y)
{if(!b) //边界情况，b=0{x = 1, y = 0; //求系数return a;}int d = exgcd(b, a % b, y, x); // 递归求最大公约数,求的是by+ax，换下xy的位置。y -= a / b * x;return d;
}int main ()
{cin >> n;while(n -- ){int a, b, m;cin >> a >> b >> m;int x, y;int d = exgcd(a, m, x, y);if(b % d)cout << "impossible" << endl;elsecout << (long long) x * (b / d) % m << endl;}return 0;}