AcWing872. 最大公约数

#include<iostream>
using namespace std;
int main()
{
    int n,a,b;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        if(a==b) 
            cout<<a<<endl;
        else
        {
            if(a<b) swap(a,b);//保证a>b;
            for(int i=b;i>=1;i--)
                if(a%i==0&&b%i==0)
                {
                    cout<<i<<endl;
                    break;
                }
        }
    }
    return 0;
}

其实由数据范围就能知道上边思路TLE

y总代码:

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

下面来讲一下求最大公约数的几种的方法:

穷举法(枚举法)

求最大公约数时从两者中较小的数开始，由大到小列举，直到找到第一个公约数为止。

#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a<b) swap(a,b);//保证a>b;
    for(int i=b;i>=1;i--)
        if(a%i==0&&b%i==0)
        {
            cout<<i<<endl;
            break;
        }
    return 0;
}

实现思路很简单，但是当数据范围很大，如涉及到多组输入的时候就会TLE.

辗转相除法

• 又称欧几里得算法。用于计算两个正整数a，b的最大公约数和最小公倍数
• 这条算法基于一个定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数（比如10和25，25除以10商2余5,那么10和25的最大公约数，等同于5和10的最大公约数）
• 即:gcd(a,b) = a (b=0)和gcd(b,a mod b) (b!=0)
• 用递归的方法来实现:首先，我们先计算出a除以b的余数c，把问题转化成求出b和c的最大公约数；然后计算出b除以c的余数d，把问题转化成求出c和d的最大公约数；再然后计算出c除以d的余数e，把问题转化成求出d和e的最大公约数......

//基本代码:
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if(a%b==0) return a;
    gcd(b,a%b);//始终让函数的第一个参数小于第二个参数
}
int main()
{
    int n,a,b;
    cin>>a>>b;
    if(a<b) swap(a,b);//保证a>=b;
    cout<<gcd(a,b)<<endl;
    return 0;
}

y总辗转相除法模板:

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
    return 0;
}

上面那个题用辗转相除法，过了.

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if(a%b==0) return b;
    gcd(b,a%b);//始终让函数的第一个参数大于第二个参数
}
int main()
{
    int n,a,b;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        if(a<b) swap(a,b);//保证a<=b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    return b?gcd(b,a%b):a;// return a?gcd(b%a,a):b;
}
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
    return 0;
}

更相减损术

• 出自于中国古代的《九章算术》，也是一种求最大公约数的算法
• 两个正整数a和b（a<b），它们的最大公约数等于b-a的差值c和较小数a的最大公约数。比如10和25，25减去10的差是15,那么10和25的最大公约数，等同于10和15的最大公约数。
• 用递归的方法来实现:

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if(b==a) return a;
    if(a<b) swap(a,b);
    gcd(a-b,a);
}
int main()
{
    int a,b;
    cin>>a>>b;
    if(a<b) swap(a,b);//保证a>=b;
    cout<<gcd(a,b)<<endl;
    return 0;
}

上面那个题用更相减损术，显示MLE

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if(b==a) return a;
    if(a<b) swap(a,b);
    gcd(a-b,a);
}
int main()
{
    int n,a,b;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        if(a<b) swap(a,b);//保证a<=b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

问题出在哪呢？
gcd(a-b,a)这个地方出问题了，应该为gcd(a-b,b);

#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    if(b==a) return a;
    if(a<b) swap(a,b);
    gcd(a-b,b);
}
int main()
{
    int n,a,b;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        if(a<b) swap(a,b);//保证a>=b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

改之前过了0/10个数据，改之后过了9/10个数据，还是显示MLE…
又做了这个题，用上面代码AC了这又是为啥.
注意:不管是辗转相除法或者更相减损术，在手写gcd时，两个参数的值很容易出错，一出错就会陷入死循环

辗转相除法和更相减损术的证明–后边再讲
还一个

STL中的__gcd()函数（为两个下划线）

#include<iostream>
#include<bits.stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<__gcd(a,b)<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>//头文件
using namespace std;
int main()
{
    int n, a,b;
    cin>>n;
    while(n--)
    {
        cin>>a>>b;
        cout<<__gcd(a,b)<<endl;
    }

    return 0;
}

提交之后的时间和手写的gcd()函数差不多

Stein算法