AcWing 872. 最大公约数（第N篇关于STL的题解）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 872. 最大公约数（第N篇关于STL的题解）原题链接简单

作者：

有猷 , 2020-01-18 18:42:04 , 所有人可见 , 阅读 6694

42

13

本人蒟蒻，题解如果有问题（肯定有）,希望大家在评论区中指出，谢谢。

本题的做法：

直接用辗转相除法求解
使用STL中的__gcd函数

本题解主要介绍的是STL做法，__gcd()函数其实和手写的GCD函数用法一样，就是方便一些
（注意！函数前面有两个下划线哦。即：是“__gcd”而不是“_gcd”）
STL代码如下：

#include<bits/stdc++.h>//万能头文件
using namespace std;//这句话一定不能忘哦！
int n,a,b;
int main() {
    cin >> n;
    while(n--){
        cin >> a >> b;
        cout << __gcd(a,b) << endl;//调用STL函数
    }
    return 0;
}

在这里，也贴一下欧几里得算法的c++代码：

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

感谢大家从头看到了尾