欧几里得算法

• 算法内容
  计算两个数的最大公约数的算法，也叫辗转相除法。即：
  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的改变。