欧几里得算法用于求解最大公因数
主要原理:
int gcd(int a,int b){return b?gcd(b,a%b):a;}
扩展欧几里得算法用于求解二元一次方程
首先了解一下裴蜀定理: <nobr> ax+by=c </nobr>有解当且仅当 <nobr> gcd(a,b)|c </nobr>
那么我们就可以求解 <nobr> ax+by=gcd(a,b) </nobr>
根据这个原理递归求解即可
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);
int temp=x;
x=y;
y=temp-a/b*y;
return GCD;
}
根据这个求得的 <nobr> x,y </nobr>只是一组可行解
如果 <nobr> gcd(a,b)=1 </nobr>,那么如果得到一组解 <nobr> x0,y0 </nobr>,通解就可以表示为 <nobr> x=x0+b×t </nobr>, <nobr> y=y0−a×t </nobr>
如果需要求最小整数解x,我们可以令 <nobr> t= b (a , b) </nobr>,那么 <nobr> x=(x0%t+t)%t </nobr>即可