欧几里得算法及其证明

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}

int gcd(int a,int b){
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    return a;
}