题目描述

算法1

(暴力枚举) $O(log(a+b))$

欧几里得和更相减损数

C++ 代码

#include<bits/stdc++.h>
using namespace std;

int gcd(int a,int b)        //欧几里得算法
{
    return b ? gcd(b,a%b) : a;
}

int gcd1(int a,int b)       //更相减损数,用于大数求最大公因数，以后加
{
    int tmp=0;
    if(a<b)
    {
        tmp=b;
        b=a;
        a=tmp;
    }
    return b ? gcd(a,a-b) : b;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        int ans;
        ans=gcd1(a,b);
        cout<<ans<<endl;
    }
    return 0;
}