欧几里得算法
- 算法内容
计算两个数的最大公约数的算法，也叫辗转相除法。即：
gcd(a,b)=gcd(b,a%b)。
- 数学证明
设gcd(a,b)=d,则必定有：d|a且d|b,则必定有d|(ax+by)而a%b=a-a/b*b,所以d|(a%b),则d必定为b和a%b的约数，并且a%b必定小于a则d必定为b和a%b的最大公约数。
-代码实现
优美，太优美了！
给定n对数a,b，求它们的最大公约数。
#include<iostream>
using namespace std;
int find(int a,int b)
{
return b?find(b,a%b):a;//优美 太优美了！！！！
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,b;
cin>>a>>b;
int res=find(a,b);
printf("%d\n",res);
}
return 0;
}
扩展欧几里得算法
- 算法作用
数论中有对于一对正整数a,b，必定存在一对x,y使得ax+by=gcd(a,b),扩展欧几里得算法可以算出这一对x,y.
- 算法内容
求解ax+by=gcd(a,b),对于特殊的当b=0时有ax+by=gcd(a,0)=a,此时有x=1,y=0。当b\(\not=\) 0时，gcd(a,b)=gcd(b,a%b),设gcd(a,b)=d,则有：
\(ax+by=bx^{\prime}+(a\%b)y^{\prime}=bx^{\prime}+(a-\frac{a}{b}*b)y^{\prime}=ay^{\prime}+b(x^{\prime}-\frac{a}{b}y^{\prime})\) 假如我们已经得到了\(y^{\prime}\)和\(x^{\prime}\)只需令\(x=y^{\prime},y=x^{\prime}-\frac{a}{b}y^{\prime}\)，也在递归过程中相邻两个过程中将xy调换就只需令\(y=y-\frac{a}{b}x\).
- 代码实现
给定n对正整数a,b，对于每组都求出一对x,y,使得ax+by=gcd(a,b)
#include<iostream>
using namespace std;
int exgcd(int a,int b,int &x,int &y)//注意这里x.y都是引用
{
if(b==0)
{
x=1,y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y=y-a/b*x;
return d;
}
int main()
{
int n;
cin>>n;
while(n--)
{
int a,b;
scanf("%d %d",&a,&b);
int x,y;
int res=exgcd(a,b,x,y);
printf("%d %d\n",x,y);
}
return 0;
}
- 代码细节
这里传参的x,y都得使用引用，这样就可以对每一个形参x,y的改变就是对x,y的改变。