GCD。

自己一直用gcd函数，原理都快不记得了，现在写这篇博客来复习一下。
比如找200和90的GCD最暴力的办法是一个for循环从2到89，找到最大的i使得200%i==0且90%i==0.
上面的办法在时间效率很慢，复杂度为O(n)。
下面讲一下辗转相除法的原理。还是200和90为例。
先贴个代码。

int GCD(int a,int b)
{
    if(a<b) swap(a,b);
    int i=a%b;//i为x除以y的余数。
    while(i!=0)
    {
        a=b;
        b=i;
        i=a%b;
    }
    return b;
}

第一步：令c=gcd(a,b)，则设a=mc，b=nc
第二步：根据前提可知r =a-kb=mc-knc=(m-kn)c
第三步：根据第二步结果可知c也是r的因数
第四步：可以断定m-kn与n互质(假设m-kn=xd，n=yd (d>1)，则m=kn+xd=kyd+xd=(ky+x)d，则a=mc=(ky+x)cd，b=nc=ycd，则a与b的一个公约数cd>c，故c非a与b的最大公约数，与前面结论矛盾)，因此c也是b与r的最大公约数。
从而可知gcd(b,r)=c，继而gcd(a,b)=gcd(b,r)。
2.辗转相减法

int GCD(int a, int b)
{
    while(a!=b)
    {
        if (a > b) a -= b;
        else b -= a;
    }
    return a;
}

更相减损法：
两个数gcd(x,y)=gcd(x,y-x).
三个数gcd(x,y,z)=gcd(x,y-x,z-y)
多个数gcd(a1,a2,a2,.....,an)=gcd(a1,a2-a1,a3-a2,.....,an-an-1);
下面放一道模板提
一道GCD:
https://ac.nowcoder.com/acm/contest/10743/A

代码的注释部分是自己做错的地方。
//由gcd定义得两个数的最大公约数为其中较小的一个。
#include<iostream>
#include<bits/stdc++.h>
#define qc std::ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef unsigned long long int ul;
typedef double dl;
int main()
{
    int n;
    int a[100005];
    int gcd;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    gcd=0;//gcd初始化为0，不能为1，0和整数m的最大公约数都为m，1与m的数都为1.
    for(int i=2;i<=n;i++)
        gcd=__gcd(a[i]-a[i-1],gcd);//由gcd(x,y,z)=gcd(x,y-x,z-y),注意__中的一个参数是上一个求的gcd。
    cout<<gcd<<" "<<(gcd-a[1]%gcd)%gcd<<endl;//将a[1]变为不大于gcd的数。
}