题解 | #最大公约数#

#include<stdio.h>
#include<math.h>
int main()
{
    //辗转相除法
    int a,b,c,sum=0;
    scanf("%d %d",&a,&b);
    while(a%b!=0)
    {
        c = a%b;
        a = b;
        b = c;
    }
    sum = b;
    printf("%d",sum);
    return 0;
}

//更相相减术
int main()
{
    int a,b,c,d=0;
    scanf("%d %d",&a,&b);
    //先从大到小排序,大的在前小的在后
    if(a<b){c = b;b = a;a = c;}
    else{a=a;b=b;}
    //判断是否都是偶数
    while(a%2==0&&b%2==0){
        a/=2;b/=2;d++;
    }
    //非全偶，用大数减去小数
    int e,f,m,result;
    e = a;f = b;m = a - b;
    while(m!=f)
    {
        e = f;
        f = m;
        m = e - f;
        if(m<0)
            m=-m;
    }
    result = m*pow(2,d);
    printf("%d",result);
    return 0;
}
//总结：第二种算法相当不适用，且复杂，在牛客网完全没法运行高数字量的输入