一、拓展欧几里得算法
1.1 算法简析
根据裴蜀定理,对任意 \(a\) 和 \(b\),一定存在 \(x\) 和 \(y\),使 \(ax + by = \text{gcd}(a, b)\)。拓展欧几里得算法不仅能求出 \(a\) 和 \(b\) 的最大公约数,而且能找到一对 \((x, y)\) 使该方程成立。
设求解 \(ax + by = \text{gcd}(a, b)\) 的函数为
int extgcd(int a, int b, int &x, int &y)
该函数返回 \(\text{gcd}(a, b)\),即 \(a\) 和 \(b\) 的最大公约数。同时,引用的 \(x\) 和 \(y\) 就是方程的一对解。
假设 \(b \neq 0\),
\(\text{extgcd(a, b, x, y)}\) 表示的方程为 \(ax + by = \text{gcd}(a, b)\)
\(\text{extgcd(b, a \% b, x', y')}\) 表示的方程为 \(bx' + (a~\%~b)y' = \text{gcd}(b, a~\%~b)\)
我们知道 \(a~\%~b\) 是取余运算,可以转换成 \(a~\%~b = a - \lfloor \frac{a}{b} \rfloor \times b\),代入方程得到 \(bx' + (a - \lfloor \frac{a}{b} \rfloor \times b)y' = \text{gcd}(b, a~\%~b)\),整理得到 \(ay' + b(x' - \lfloor \frac{a}{b} \rfloor \times y') = \text{gcd}(b, a~\%~b)\)
\[\begin{split} &\because b \neq 0 \\ &\therefore \text{gcd}(a, b) == \text{gcd}(b, a~\%~b) \\ &\therefore 两个方程的左式是相等的 \\ \\ &ax + by = ay' + b(x' - \lfloor \frac{a}{b} \rfloor \times y') \\ &\therefore x=y',~y=x' - \lfloor \frac{a}{b} \rfloor \times y' \end{split} \]假设 \(b == 0\),
\(\text{extgcd(a, b, x, y)}\) 表示的方程为 \(ax = \text{gcd}(a, 0) = a\),可以得到特解 \(x=1,~y=0\)。
因此,我们可以采用递归的方式定义函数。
1.2 模板
ll extgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
ll ret = extgcd(b, a % b, y, x);
y -= (a / b) * x;
return ret;
}
1.3 通解
\(\text{extgcd(a, b, x, y)}\) 可以得到 \((x_0, y_0)\) 这一个特解,通解为
\[x=x_0+k\frac{b}{\text{gcd}(a,b)},~y=y_0-k\frac{a}{\text{gcd}(a,b)} \]二、相关题目
2.1 题目描述
2.2 问题简析
题目要求 \(ax \equiv 1~(\text{mod}~b)\) 的最小正整数解。因为拓展欧几里得算法求解方程的格式为 \(ax + by = \text{gcd}(a, b)\),所以要对原式进行转化。
\[\begin{split} &\because by \equiv 0~(\text{mod}~b)\\ &\therefore ax+by \equiv 1~(\text{mod}~b) \\ \\ &令~ax+by=1\\ 由裴蜀定理&,若该方程有解,则~\text{gcd}(a, b) = 1\\ \\ \therefore~求~ax+by&=\text{gcd}(a, b)~成立的最小正整数~x \end{split} \]至此,我们可以直接套用上文的模板求解。需要注意的是,本题要求的是 \(x\) 的最小正整数解,所以求出 \(x_0\) 后要进行处理:
x = (x % b + b) % b;
2.3 AC代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, x, y;
ll extgcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
ll ret = extgcd(b, a % b, y, x);
y -= (a / b) * x;
return ret;
}
int main()
{
cin >> a >> b;
extgcd(a, b, x, y);
cout << (x % b + b) % b << endl;
return 0;
}
完
标签:frac,gcd,text,欧几里得,拓展,算法,ax,ll,extgcd From: https://www.cnblogs.com/hoyd/p/18070761