数论复习_欧几里得算法与扩展欧几里得算法

在小学二年级，我们学过欧几里得算法，又叫辗转相除法。

其代码描述为：

ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}

 当然对于我们这种学过STL的何必写上面的傻逼代码

直接调用__gcd(a, b)这个函数即可求解两个数的最大公因数。

欧几里得算法告诉我们一件事情：

两个数的最大公因数等于较小的那个数和他们两个余数的最大公因数

证明过程

 然而事实上我们需要会用这个结论即可

同时最小公倍数等于a*b/gcd(a, b)

然而这些并不是重点~

重点是扩展欧几里得算法

首先，扩展欧几里得算法需要解决的问题是

已知方程：ax+by=gcd(a, b)（这个等式又叫做贝祖等式）

由几千年前一个大佬的结论可以知道在a, 一定存在整数x, y使得上述结论成立

如何求解这个x, y就需要用到扩展欧几里得算法

代码实现：

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

 在实际应用之中不会存在这么直接的问题，利用扩展欧几里得算法，我们可以求解乘法逆元

介绍一些杂七杂八的定理：

乘法逆元：

如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x。下文中，x都表示乘法逆元。

费马小定理：

求乘法逆元的方法：写成ax + py = 1的形式求出来的x就是a的逆元

a/b=a/b*(b * b ^ (M-2))=a*(b ^ (M-2)) (mod M)

来几道例题

题目一

扩展欧几里得算法裸题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}
void exgcd(ll a, ll b, ll &x, ll &y) {
	if(b == 0) {
		x = 1;
		y = 0;
		return;
	}
	else {
		exgcd(b, a % b, x, y);
		ll temp = x;
		x = y;
		y = temp - a / b * y;
	}
}
int main () {
	ll A, B;
	ll x, y;
	while(cin >> A >> B) {
		exgcd(A, B, x, y);
		cout << x << " " << y << " " << gcd(A, B) << endl;
	}
}
/*
4 6
17 17
*/

题目二

非常经典的题目

列出方程得到相应的方程，变形转化为扩展欧几里得算法求解的方程如果不能求解，说明不能碰面

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}
void exgcd(ll a, ll b, ll &x, ll &y) {
	if(b == 0) {
		x = 1;
		y = 0;
		return;
	}
	else {
		exgcd(b, a % b, x, y);
		ll temp = x;
		x = y;
		y = temp - a / b * y;
	}
}
int main () {
	ll x, y, m, n, l;
	cin >> x >> y >> m >> n >> l;
	ll t, k;
	if((x - y) % gcd(n - m, l)) {
		cout << "Impossible" << endl;
	}
	else {
		exgcd(n - m, l, t, k);	
		t = t * (x - y) / gcd(n - m, l);
		t = (t % l + l) % l;
		cout << t << endl;
	}
	
	
}

题目三

与上题有相似之处，列出扩展欧几里得方程，运用板子求解。当然该题也可以用费马小定理转化为幂的形式，然后用快速幂求解。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
	return b == 0 ? a : gcd(b, a % b);
}
void exgcd(ll a, ll b, ll &x, ll &y) {
	if(b == 0) {
		x = 1;
		y = 0;
		return;
	}
	else {
		exgcd(b, a % b, x, y);
		ll temp = x;
		x = y;
		y = temp - a / b * y;
	}
}
int main () {
	int T;
	cin >> T;
	while(T--) {
		ll n, B;
		cin >> n >> B;
		ll ans, sb;
		exgcd(B, 9973, ans, sb);
		ans *= n;
		ans = (ans % 9973 + 9973) % 9973;
		cout << ans << endl;
	}
}

综上是一些数论的最基础的知识复习，看了博客有问题可以私聊或者留言，以后会继续更新相关的数论知识~

更新于：2020-10-07　　20:08:39