gcd以及exgcd
一、前言
gcd也就是欧几里得算法也称辗转相除法，是一种求解最大公约数的算法
exgcd是扩展欧几里得算法，该算法在gcd的基础上增加了一个求解二元一次不定方程的解
二、
1.GCD
由于gcd较为简单，这里不加以证明，故给出代码：
1 #include "bits/stdc++.h" 2 using namespace std; 3 int gcd(int a,int b) 4 { 5 if(b == 0) return a; 6 else return gcd(b,a % b); 7 } 8 int main() 9 { 10 int a,b; 11 cin >> a >> b; 12 cout << gcd(a,b) << endl; 13 return 0; 14 }
2.EXGCD（扩展欧几里得定理）
给出如下证明：
//前提是要保证a和b互质的情况下才可以使用哦
//求解一个不定方程的解ax + by = gcd(a,b)这个方程会有多个解
//当b为0时，有一组特殊的解x=1,b=0; //当b>0时，我们可以找到一组特殊的解可以表示整个不定方程的解 //若a,b为正整数，则我们一定能找到一组解是的ax + by = gcd(a,b) //列如gcd(6,10) = 2,6 * （2） + 10 * （-1） = 2 //设ax + by = gcd(a,b) //又因为gcd(a,b) = gcd(b,a%b) //所以ax + by = by + a%b*x //又因为a % b = a - a / b * b 证明：令a=ib+c 则 a % b = c i * b + c - i * b //所以a%b == a - a / b * b //接上证明exgcd ax + by = by + (a - a/b * b) *x // ax + by = by + ax -a/b*b*x // ax + by = ax + b(y - a/b*x) // 可以看出x等于上一次的x0,y = (y0 - a / b * x0) // 所以我们可以在求出最大公约数的同时求出一个解 代码实现：#include "bits/stdc++.h" using namespace std; int exgcd(int a,int b,int &x,int &y) { if(b == 0){ x = 1; y = 0; return a; } else{ int d = exgcd(b,a % b,y,x);//这个一定要在上面，因为首先要先求到最特殊解，然后一层层往上求解一个正解 y = y - a/b * x;//对应证明公式部分,等于上一次的y经过这些运算会得到一个新y值 return d; } } int main() { int a,b; int x,y; cin >> a >> b; int d = exgcd(a,b,x,y); cout << x << ',' << y << ',' << d << endl; return 0; }
三、总结
这两天学会了一些基本的数论方法，特别是学会了证明，感觉还是不错的！