AcWing 877. 扩展欧几里得算法
给定n对正整数ai,bi，对于每对数，求出一组xi,yi，使其满足ai?xi+bi?yi=gcd(ai,bi)。
输入格式
第一行包含整数n。
接下来n行，每行包含两个整数ai,bi。
输出格式
输出共n行，对于每组ai,bi，求出一组满足条件的xi,yi，每组结果占一行。
本题答案不唯一，输出任意满足条件的xi,yi均可。
数据范围
1≤n≤105,
1≤ai,bi≤2?109
输入样例：
2
4 6
8 18
输出样例：
-1 1
-2 1
扩展欧几里得算法：
裴蜀定理：对于任意正整数a, b,一定存在非零整数x, y,使得ax + by = gcd(a, b) = d;
d是a, b的最大公约数, d是a和b的倍数，则一定存在ax + by = d.
当b = 0时，(a, 0) = a, a* 1 + b* 0 = a, x = 1, y = 0;
当b ≠ 0时，(a, b) = (b, a % b) = d.
a % b = a - a/b * b;
by + (a - a/b * b)x = d;
ax +b(y - a/b* x) = d;
x’ = x, y’ = y - a/b* x.
Code:
#include <iostream>
#include <cstdio>
using namespace std;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 = y - a / b * x;return d;
}int main()
{
int n;scanf("%d", &n);while(n --){
int a, b, x, y;scanf("%d%d", &a, &b);int res = exgcd(a, b, x, y);printf("%d %d\n", x, y);}return 0;
}
AcWing 878. 线性同余方程
给定n组数据ai,bi,mi，对于每组数求出一个xi，使其满足ai?xi≡bi(mod mi)，如果无解则输出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
7
算法思路：
ax ≡ b (mod m)等价于 存在整数y,使得 ax = my + b → ax - my = b → ax + my’ = b.
当 b 能够整除 a 和 m 的最大公约数d，则该式有解. 先用扩展欧几里得算法算出ax + my’ = d对应的x值，因为b能整除d, 等式两边乘以 b/d, 则等式的右边就转化为题目所给的b，所求得x = x * (b / d）% m.
Code:
#include <iostream>
#include <cstdio>
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 = 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) puts("impossible");else printf("%d\n", (LL) x * (b / d) % m);}return 0;
}