拓展欧几里得、逆元、线性同余方程、中国剩余定理和拓展中国剩余定理

拓欧介绍

简单来说，拓欧就是求关于x，y的方程$ax+by=gcd(a,b)$的所有整数解。

这里就简单的证一下，详细证明点这里

由欧几里得定理可以得出$gcd(a,b)=gcd(b,a \%\ b)$。

由$gcd(b,a \%\ b)=bx_1+(a \%\ b)y_1$

由于$(a\%\ b)$可以表示成$a-(a/b)*b$。

所以表示成$bx_1+ay_1-b(a/b)y_1$。

即$ay_1+b(x_1-(a/b)y_1)$。

由于式子右边相当，所以左边也相等。

所以推出$x==y_1$,$y==x_1-(a/b)y_1$。

当我们推到最后一步的时候，即$b==0$时，显然是存在一组特解$x_1==1,y_1==0$。

那么我们就可以用这个特解来推出其他的解了。

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

逆元介绍

若整数$b,m$互质（这点很重要），并且$b|a$（表示b能整除a），则存在一个整数$a/b\equiv a*x(mod \ m) $

称x为b的逆元。

介绍一下求逆元比较常用的两种方法。

1、快速幂求逆元

如果模数m为质数，由费马小定理的$b^{p-2}$为b的逆元。

可以用快速幂求出$b^{\ p-2}$。

2、拓欧求逆元

由定义知，$a\times x\equiv 1(mod\ m)$，这个x就是a的逆元,等价于$a\times x-1$是m的倍数。

将这个倍数令为-y倍。

得到$a\times x+m\times y=1$。

我们只需要用拓展欧几里得求得x，在令x对m取模即可。

线性同余方程介绍

给定你a和b，以及取余的m，求一个整数x满足$a*x\equiv b(mod\ m)$。

求x的最小值。

这个方程$a*x\equiv b(mod\ m)$就是线性同余方程。

等价于$a\times x+m\times y=b$。

这个方程有解需要满足$gcd(a,m)|b$。（注意）

我们可以用拓欧来求出一组特解$x_0,y_0$。

通解为$x = x_0+(m/t)\times z$，$y = y_0\ +(a/t)\times z$，其中t为$gcd (a,m)$,z为整数。

因为$lcm(a,b) = a*b/gcd(a,b)$。

即每次增加一个最小公倍数。

当我们要求$a\times x+m \times y=b$的解时，我们可以先求出$a \times x +m\times y=gcd(a,m)$的解$x_0$。

那么原方程的解为$x=x_0*b/gcd(a/m)$，其中$b/gcd(a,m)$为扩大的倍数。

典型例题

洛谷-P1082 同余方程

题目大意

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

解题思路

就是模板题。输入数据保证有解，不需要再去判断是否满足条件。

完整代码

#include <iostream>
using namespace std;

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

int main() {
	int a, b, x, y;
	cin >> a >> b;
	ex_gcd(a, b, x, y);
	x = (x%b + b) % b;
	cout << x << endl;
}

中国剩余定理介绍

求解同余方程组

$\begin{cases} x \equiv a_1(mod\ m_1) \\ x \equiv a_2(mod\ m_2) \\ x\equiv a_3(mod\ m_3) \\ ……………. \\ x \equiv a_k(mod\ m_k) \end{cases}$

其中$m_1,m_2,m_3,….,m_k$为两两互质的整数。（这个区别于拓展中国剩余定理）

求x的最小非负整数解。

令$M=∏^k_{i = 1\ m_i}$，（$∏$这个符号代表连乘），即M是所有$m_i$的最小公倍数。

$t_i$是同余方程$\frac{M}{m_i}\equiv 1(mod\ m_i)$的最小非负整数解。

则解x为$x=∑^k_{i=1}\ a_i\frac{M}{m_i}t_i$。

通解为$x+i*M$。

最小非负整数解为$(x %M+M) %M$。

证明的话，蓝书证明的挺好的，这里就不写了。

典型例题

洛谷-P3868 猜数字

题目大意

现有两组数字，每组 k 个。

第一组中的数字分别用 $a_1,a_2,\cdots ,a_k$ 表示，第二组中的数字分别用 $b_1,b_2,\cdots ,b_k $表示。

其中第二组中的数字是两两互素的。求最小的 $n∈N$，满足对于 $\forall i\in [1,k]，有 b_i | (n-a_i)$。

解题思路

把 $b_i | (n-a_i)$变一下型，就变成了$n\equiv a_i(mod \ b)$。

就是一个模板题了。

补充：

如果有$a\equiv b(mod \ m)$，则$a+c\equiv b\ +c(mod\ m)$成立。

完整代码

#include <iostream>
using namespace std;

typedef long long ll;
ll a[20], b[20];
int n;

ll exgcd(ll a, ll b, ll& x, ll& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	ll t = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return t;
}

ll qmul(ll a, ll b, ll mod) {//快速乘
	ll ans = 0;
	while (b) {
		if (b & 1)	ans = (ans + a) % mod;
		a = (a << 1) % mod;
		b >>= 1;
	}
	return ans;
}

ll china() {
	ll M = 1, ans = 0;
	for (int i = 1; i <= n; i++)	M *= b[i];
	for (int i = 1; i <= n; i++) {
		ll t = M / b[i];
		ll x, y;
		exgcd(t, b[i], x, y);
		x = (x % b[i] + b[i]) % b[i];
		ans = (ans + qmul(qmul(a[i], t, M), x, M)) % M;
	}
	return (ans%M+M)%M;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) cin >> b[i];
	for (int i = 1; i <= n; i++) a[i] = (a[i] % b[i] + b[i]) % b[i];//题目中的a可能大于b，所以需要取模
	ll ans = china();
	cout << ans << endl;
}

拓展中国剩余定理介绍

求解同余方程组

$\begin{cases} x \equiv a_1(mod\ m_1) \\ x \equiv a_2(mod\ m_2) \\ x \equiv a_3(mod\ m_3) \\ ……………. \\ x \equiv a_k(mod\ m_k) \end{cases}$

其中$m_1,m_2,m_3,….,m_k$为不一定两两互质的整数。

求x的最小非负整数解。

我们可以设第i项的解$x_i$为$x_i = x_{i-1}+k_{i-1}*M$​。其中M为前$i-1$项的m的最小公倍数。

将$x_i$带入式子得$k_{i-1}\times m_{i-1}-k_i\times m_i+x_{i-1}\equiv a_i(mod\ m_i)$。

即$k_{i-1}\times M-k_i\times m_i\equiv a_i-x_{i-1}(mod\ m_i)$。

我们可以用拓欧来求出$k_{i-1}$，然后带入到$x_i = x_{i-1}+k_{i-1}*M$中，求得$x_i$。

典型例题

洛谷-P4777 【模板】扩展中国剩余定理（EXCRT）

题目大意

求解同余方程组

$\begin{cases} x \equiv b_1(mod\ a_1) \\ x \equiv b_2(mod\ a_2) \\ x \equiv b_3(mod\ a_3) \\ ……………. \\ x \equiv b_k(mod\ a_k) \end{cases}$

求x的最小非负整数解。

解题思路

模板题，套板子即可，注意快(gui)速乘。

完整代码

#include <iostream>
using namespace std;

typedef long long ll;
const int N = 1e5 + 5;
ll a[N], b[N];
int n;

ll exgcd(ll a, ll b, ll& x, ll& y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	ll t = exgcd(b, a % b, y, x);
	y -= (a / b) * x;
	return t;
}

ll qmul(ll a,ll b,ll mod) {
	ll ans = 0;
	while (b) {
		if (b & 1)	ans = (ans + a % mod) % mod;
		a = (a << 1) % mod;
		b >>= 1;
	}
	return ans;
}

bool get_ans(ll a, ll b, ll c, ll& x, ll& y, ll& gcd) {
	gcd = exgcd(a, b, x, y);
	ll k = c / gcd, t = b / gcd;
	if (c % gcd)	return false;
	x = qmul(x, k, t);
	x = (x % t + t) % t;
	return true;
}

ll exchina(ll& ans) {
	ll x, y,gcd;
	ll M = a[1];
	for (int i = 2; i <= n; i++) {
		if (!get_ans(M, a[i], (b[i] - ans % a[i] + a[i]) % a[i], x, y, gcd))
			return false;
		ans += M * x;
		M = M / gcd* a[i] ;
		ans = (ans % M + M) % M;
	}
	return true;
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++)	cin >> a[i] >> b[i];
	ll ans = b[1];
	exchina(ans);
	cout << ans << endl;
}

到这里，就差不多把我最近学的数论方面的东西讲完了。。

（数论是真的难啊啊

简直是天书。。