AcWing 872. 最大公约数

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 872. 最大公约数原题链接简单

作者：

贺谦 , 2020-05-05 10:05:58 , 所有人可见 , 阅读 587

题目描述

给定n对正整数ai,bi，请你求出每对数的最大公约数。

样例

2
3 6
4 6

3
2

算法

(欧几里得算法)

１．刚开始对a整除b不太懂，百度了一下，看这里。

时间复杂度

$O(log min(a, b))$

C++ 代码

 **#include <iostream>

using namespace std;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

int main()
{
    int n;
    scanf("%d", &n);
    while(n --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", gcd(a, b));
    }

    return 0;
}**

10 评论

贺谦 2020-05-05 21:32

时间复杂度刚开始写错了，写成了$O(n)$的，应该是$O(logmin(a, b))$的。这里有一个证明，大家可以瞅瞅~
https://blog.csdn.net/xiamentingtao/article/details/44702869?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1

Codecat 2020-05-05 10:21

为什么不用pair呢

贺谦 2020-05-05 21:10

你有写pair版的吗

Codecat 2020-05-05 21:27 回复了贺谦的评论

https://www.acwing.com/problem/content/submission/code_detail/1480703/
有点勉强强行pair

贺谦 2020-05-05 21:31 回复了 Codecat 的评论

好的，我学习下。

贺谦 2020-05-05 21:33 回复了 Codecat 的评论

怎么404了。。

Codecat 2020-05-05 21:36 回复了贺谦的评论

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


int main(){
    int n=0;
    cin>>n;
    for(int i=0;i<n;i++){
        int x,y;
        cin>>x>>y;
        pair<int,int>a (x,y);
        cout<<gcd(a.first,a.second)<<endl;
    }



    return 0;
}