【算法】欧几里得与拓展欧几里得算法

一、欧几里得算法

二、拓展欧几里得算法

2.1 裴蜀定理

2.2 拓展欧几里得算法

2.3 例题

三、线性同余方程

3.1 概念

3.2 例题

一、欧几里得算法

欧几里得算法又称辗转相除法，可用于求解两个数的最大公约数

其思路：

gcd(a, b) = gcd(b, a%b)，其中gcd(a, b)代表a和b的最大公约数
当b=0时，a为最大公约数

例如要求36和24的最大公约数即gcd(36, 24)，可转而求gcd(24, 36%24)即gcd(24, 12)，再转为求gcd(12, 0），此时最大公约数即为12

其代码实现：

int gcd(int a, int b)
{if(b == 0)return a;return gcd(b, a % b);
}

二、拓展欧几里得算法

2.1 裴蜀定理

若a，b是整数，且d = gcd(a, b)，则对于任意的整数x和y，总有ax+by是d的倍数
对于给定的整数x和y，方程ax+by=c有整数解(x, y)的充分必要条件是c是gcd(a, b)的倍数

2.2 拓展欧几里得算法

由裴蜀定理，我们知道对于给定的整数a和b，方程ax + by = gcd(a, b)总有整数解(x, y)

那么，如何求出这个整数解(x, y)？

由欧几里得算法可得gcd(a, b) = gcd(b, a%b)
由裴蜀定理，bx' + (a%b)y' = gcd(b, a%b)
由1和2，得bx' + (a%b)y' = gcd(a, b) 即 ax + by = bx' + (a%b)y'
由a%b = a - b*(a/b)【注意这里的a/b是向下取整】，得ax + by = bx' + [a - b*(a/b)]y'
上式整理得a(x-y') - b[x' - y - (a/b)y'] = 0，即x-y'=0、x' - y - (a/b)y'=0
得x = y'，y = x'-(a/b)y'

得到求解后，我们就可以通过递归不断传入x和y来计算整数解(x, y)了。拓展欧几里得的递归终点和欧几里得的终点类似，当b为0时即ax+by = a时返回{x=1,y=0}的解，并通过上一次的结果向下更新

拓展欧几里得算法的代码实现：

int exgcd(int a, int b, int &x, int &y) //扩展欧几里得算法
{if(b == 0) //b为0时结束递归{x = 1; //ax+by=a->x=1,y=0y = 0;return a;}int gcd = exgcd(b, a%b, y, x); //递归求x'和y'y -= (a/b) * x; //此时递归后x=y'，y=x'，将y=x'-(a/b)y'转为y=y-(a/b)x得y-=(a/b)x return gcd;
}

2.3 例题

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;int n, a, b, x, y;int exgcd(int a, int b, int &x, int &y) //扩展欧几里得算法
{if(b == 0) //b为0时结束递归{x = 1; //ax+by=a->x=1,y=0y = 0;return a;}int gcd = exgcd(b, a%b, y, x); //递归求x'和y'y -= (a/b) * x; //此时递归后x=y'，y=x'，将y=x'-(a/b)y'转为y=y-(a/b)x得y-=(a/b)x return gcd;
}void solve()
{cin >> n;for(int i = 0;i < n; i++){cin >> a >> b;exgcd(a, b, x, y);cout << x << " " << y << endl;}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

三、线性同余方程

3.1 概念

线性同余方程ax ≡ b(mod m)，要求我们求出一个整数x，使得a和x的乘积模上m等于b

对于这个方程，可以用拓展欧几里得算法求解：

ax ≡ b(mod m)可转化为对于整数x，存在整数y使得ax = my + b
令y' = -y，则上式转化为ax + my' = b
用拓展欧几里得算法求ax' + my' = gcd(a, m)
只要b是gcd(a, m)的倍数则说明方程成立，整数x存在，x = x' * (b / gcd(a, m))

3.2 例题

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define debug(x) cout << #x << " = " << x << '\n'
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;int n, a, b, m, x, y;int exgcd(int a, int b, int &x, int &y) //扩展欧几里得算法
{if(b == 0) //b为0时结束递归{x = 1; //ax+by=a->x=1,y=0y = 0;return a;}int gcd = exgcd(b, a%b, y, x); //递归求x'和y'y -= (a/b) * x; //此时递归后x=y'，y=x'，将y=x'-(a/b)y'转为y=y-(a/b)x得y-=(a/b)x return gcd;
}void solve()
{cin >> n;for(int i = 0;i < n; i++){cin >> a >> b >> m;int gcd = exgcd(a, m, x, y);if(b % gcd == 0) //b是gcd倍数：成立cout << x * (b / gcd) % m << endl; //为什么要%m？因为可以保证x在int范围内且同余belse //b不是gcd倍数：无解cout << "impossible" << endl;}
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;// cin >> t;while (t--)solve();return 0;
}

完.