数论-扩展欧几里得
简介
扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式 a ? x + b ? y = g c d ( a , b ) a*x+b*y=gcd(a,b) a?x+b?y=gcd(a,b)。
流程
【数论-扩展欧几里得】为求解 a ? x + b ? y = g c d ( a , b ) a*x+b*y=gcd(a,b) a?x+b?y=gcd(a,b) ①，
根据普通欧几里得算法， g c d ( a , b ) = g c d ( b , a % b ) gcd(a,b)=gcd(b,a\%b) gcd(a,b)=gcd(b,a%b) ，
假设我们已经求出了一组数 x 2 , y 2 x_2,y_2 x2?,y2?,满足 b ? x 2 + ( a % b ) ? y 2 = g c d ( b , a % b ) b*x_2+(a\%b)*y_2=gcd(b,a\%b) b?x2?+(a%b)?y2?=gcd(b,a%b) ②,
结合以上三个式子，则有 b ? x 2 + ( a % b ) ? y 2 = g c d ( b , a % b ) = g c d ( a , b ) = a ? x + b ? y b*x_2+(a\%b)*y_2=gcd(b,a\%b)=gcd(a,b)=a*x+b*y b?x2?+(a%b)?y2?=gcd(b,a%b)=gcd(a,b)=a?x+b?y，
可推知 x 1 = y 2 x_1=y_2 x1?=y2?，y 1 = x 2 ? a b ? y 2 y_1=x_2-\frac{a}{b}*y_2 y1?=x2??ba??y2?。
问题转化成了求解 x 2 x_2 x2?， y 2 y_2 y2?。
可以发现，式③的形式与式①完全相同，可以用求解式①的方式求解。
不断重复以上过程，直到 y k y_k yk?的系数为0时，得到式k的一组可行解 x k x_k xk?， y k y_k yk?,
不断将求得的解带回上一层，最终求得式①的一组可行解x，y。
#include
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
if (b==0)
{
x=1,y=0;
return a;
}
int gcd=exgcd(b,a%b,x,y),t=x;
x=y,y=t-(a/b)*y;
return gcd;
}
int main()
{
int x,y,a,b;
cout<<"求解：ax+by=gcd(a,b)\na=";
cin>>a;
cout<<"b=";
cin>>b;
cout<<"gcd(a,b)="<
推荐阅读
- Unity和Android通信系列文章2——扩展UnityPlayerActivity
- PHP|PHP 扩展开发检测清单（扩展开发必读）
- 知识扩展-SQL查询基础
- laravel|laravel 添加扩展包步骤
- bgo:|bgo: 具备扩展性的 go 程序构建工具
- Centos8中如何更改文件夹中多个文件的扩展名
- chrome插件教程2-一个简单的chrome扩展
- 为BFE编写扩展插件(1)|为BFE编写扩展插件(1) – 回调点
- 学习PHP中的高精度计时器HRTime扩展
- 欧几里得算法