拓展欧几里得证明
看了许久书终于从似懂非懂走了出来
设ax+by=gcd(a,b),解出符合条件的x,y;
当b=0时,很显然有一组必然解,x=1,y=0,即1a+00=gcd(a,b)=a;
即我们讨论b!=0的情况;
【拓展欧几里得证明】ax+by=gcd(a,b)=gcd(b,a%b);
令一组解x1,y1使得x1b+y1(a%b)=gcd(b,a%b) =gcd(a,b) = ax+by;
a/b=k…r,k=a/b下取整,所以a%b=a-(a/b向下取整b);
所以x1b+y1( a-(a/b向下取整b) ) 化简得
y1*a+b(x1-y1(a/b向下取整))
所以x=y1,y=x1-y1(a/b向下取整)
x1,y1,在下层已经求得,从而递推出x,y,最下面一层的解为x=1,y=0;
#include
#include
#include
#include
#include
using namespace std;
exgcd(int a,int b,int &d,int &x,int &y){
if(!b){x=1,y=0;
d=a};
else{
exgcd(b,a%b,d,x,y);
int t=x;
x=y;
y=t-y*(a/b);
}
}
推荐阅读
- v-charts简单使用
- 华为应用市场2021年度榜单揭晓(汇聚品质应用,拓展全新生态)
- VuePress|VuePress 博客优化之拓展 Markdown 语法
- 欧几里得算法
- 板子|扩展欧几里得算法证明(exgcd)
- 当我真正理解了扩展欧几里得定理
- 类欧几里得算法|[类欧几里得算法 数论] BZOJ 2987 Earthquake
- 线段树|[类欧几里得算法 线段树] BZOJ 1938 [CROATIAN2010] ALADIN
- 药物研发中的方法开发(二)拓展篇|译
- 【扩展欧几里得】练习题