扩展欧几里得算法 exgcd

https://en.wikipedia.org/wiki/Bézout's_identity
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

最大公约数

$x$ 和 $y$ 最大的公共约数，称为最大公约数。
在小学数学，我们一般用短除法来求最大公约是。
在计算机中一个一个试除是非常慢的，往往用扩展欧几里得实现。

ax + by = gcd(x, y)

已知 $x, y$ 求 $ax + by = \gcd(x, y)$ 的一组解 $(a, b)$ 。
显然如果将 $a$ 增加 $y$ ， $b$ 减少 $x$ ，可以得到一组新的解，目标是找到 $|a| + |b|$ 最小的一组解。

int exgcd(int x, int y, int &a, int &b) {
    if (y == 0) {
        return a = 1, b = 0, x;
    } else {
        int g = exgcd(y, x % y, b, a);
        b -= x / y * a;
        return g;
    }
}

当 $y = 0$ 时， $1 x + 0 y = x = \gcd(x, y)$ 。
注意到 $x = \lfloor x / y \rfloor y + (x \bmod y)$
$b'y + a (x \bmod y) = \gcd(a, b)$
$b'y + a (x - \lfloor x / y \rfloor y) = \gcd(a, b)$
$a x+ (b' - \lfloor x / y \rfloor a)y = \gcd(a, b)$
因此 $b = (b' - \lfloor x / y \rfloor a)$

例子

a = 2, b = 0
find x, y
ax + by = 2

1 * 2 + 0 * 0 = 2
1 * 2 + 0 * (4 - 2 * 2) = 2
1 * 2 + 0 * 4 = 2
1 * (6 - 1 * 4) + 0 * 4 = 2
1 * 6 + (-1) * 4 == 2
1 * 6 + (-1) * (10 - 1 * 6) = 2
2 * 6 + (-1) * 10 = 2
2 * (46 - 4 * 10) + (-1) * 10 = 2
2 * 46 - 9 * 10 = 2
2 * 46 - 9 * (240 - 5 * 46) == 2
47 * 46 - 9 * 240 = 2

模任意数的乘法逆元

只要互质就可以求乘法逆元

合并两个同余方程

已知 $x \bmod p_1 = r_1$ 和 $x \bmod p_2 = r_2$ 。
希望把他们合并成一个模 $\mathrm{lcm}(p1, p2)$ 的方程，或者说明无解，可以用扩展欧几里得。
设 $x = k1 p1 + r1 = k2 p2 + r2$ 。
解出 $k1 p1 - k2 p2 = r2 - r1$ 的一组解 $(k1, k2)$
新方程为
$x \bmod \mathrm{lcm}(p1, p2) = k1 p1 + r1 = k2 p2 + r2$ 。

裴蜀定理

参考资料

扩展欧几里得算法

参考题目

P1082 [NOIP2012 提高组] 同余方程

https://www.luogu.com.cn/problem/P1082

题目描述

求关于 $x$ 的同余方程 $a x \equiv 1 \pmod {b}$ 的最小正整数解。

输入格式

一行，包含两个正整数 $a,b$ ，用一个空格隔开。

输出格式

一个正整数 $x_0$ ，即最小正整数解。输入数据保证一定有解。

样例 #1

样例输入 #1

3 10

样例输出 #1

提示

【数据范围】

对于 40%的数据， $2 ≤b≤ 1,000$ ；

对于 60%的数据， $2 ≤b≤ 50,000,000$ ；

对于 100%的数据， $2 ≤a, b≤ 2,000,000,000$ 。

NOIP 2012 提高组第二天第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
void exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return;
	} else {
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
}
int main() {
	int a, b, x, y;
	cin >> a >> b;
	exgcd(a, b, x, y);
	if (x < 0) {
		x += b;
		y -= a;
	}
	cout << x << endl;
}

题解

乘法逆元
直接扩展欧几里得

模合数
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
扩展欧几里得
a * x + b * y = gcd(a, b)
|x| + |y| 越小越好

输入 a 和 b，保证 a 和 b 互质
求a x % b == 1
a x + b y == 1

需要注意最终求出的 x 可能是负数

P2613 【模板】有理数取余

https://www.luogu.com.cn/problem/P2613

题目描述

给出一个有理数 $c=\frac{a}{b}$ ，求 $c \bmod 19260817$ 的值。

这个值被定义为 $bx\equiv a\pmod{19260817}$ 的解。

输入格式

一共两行。

第一行，一个整数 $a$ 。
第二行，一个整数 $b$ 。

输出格式

一个整数，代表求余后的结果。如果无解，输出 Angry!。

样例 #1

样例输入 #1

233
666

样例输出 #1

18595654

提示

对于所有数据，保证 $0\leq a \leq 10^{10001}$ ， $1 \leq b \leq 10^{10001}$ ，且 $a, b$ 不同时是 $19260817$ 的倍数。

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[10020];
int a[10020];
int p = 19260817;
int read() {
	// 读入一个数字mod p的结果 
	scanf("%s", s);
	int n = strlen(s);
	for (int i = 0; i < n; i++) {
		a[i] = s[n - i - 1] - '0';
	}
	int u = 0;
	for (int i = n - 1; i >= 0; i--) {
		u = u * 10 + a[i];
		u %= p;
	}
	return u;
}
long long pw(long long x, long long y, long long p) {
	long long re = 1;
	for (; y; y >>= 1) {
		if (y & 1) {
			re = re * x % p;
		}
		x = x * x % p;
	}
	return re;
}
int main() {
	int A = read();
	int B = read();
	if (B == 0) {
		printf("Angry!");
	} else {
		cout << (A * pw(B, p - 2, p) % p) << endl;
	}
}

题解

直接扩展欧几里得

CF1244C The Football Season

https://codeforces.com/problemset/problem/1244/C
https://www.luogu.com.cn/problem/CF1244C