《 九章算术》记载的“中华更相减损术”可快速计算正整数a和b的最大公约数，其过程如下：

Question

令p = 1
若a和b不都是偶数，则转到第5行
令p = px2，a = a/2, b = b/2
转到第2行
令t = |a - b|
若t = 0, 则返回并输出 axp
若t为奇数，则转到第10行
令t = t/2
转到第7行
若a ≥ b, 则令a = t; 否则，令 b=t
转到第5行

1. 按照上述流程，编写一个算法 int gcd(int a, int b)，计算a和b的最大公约数；
2. 分析该算法的渐进时间复杂度

Answer 1

int gcd(int a, int b)
 {
    int ads=1;   //为求最大公约数定初值
   
    while(a%2==0&&b%2==0)
    {
        a/=2;b/=2;
        ads*=2;       //把a,b中的2^n都提出来
    }
    while(a!=b)      //直到a和b相等
    {                      //也可理解为直到所得的 减数 与 差 相等为止
        if(a>b)  a-=b;
        else    b-=a;
    }
    ads*=a;           //把最后一次循环所得减数 或者 差乘以前面的2^n
    return ads;
 }
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d",gcd(a,b));
    return 0;
}