题解 | #更相减损术#

使用 STL，不符合题目要求

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

}

自己实现一个 gcd()，内含三目运算符

但是这个还是不符合要求，因为用的是辗转相除法

#include<bits/stdc++.h>
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);
}

符合要求的正解

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(a==b) return a;
    if(a>b) return gcd(a-b,b);
    return gcd(b-a,a);
}
int main(){
    int a,b;
    cin>>a>>b;
    cout<<gcd(a,b);
}

这个在输入的数字较小的时候跑起来反而更慢些，而辗转相除法因为用到取模遇到大数时会慢些，个人认为还是前者更为实用。