P1006 7unar与最大公约数

一.解题思路

1.碎碎念

显然社长听取了我P1004题解的抱怨，背景质量显著提高，但是这时就有聪明的小伙伴要说了

啊flying flying，那你为什么不在P1005的题解说这些！

好问题！因为我不会转二进制来着，还有事吗 呜呜呜😭😭😭

2.题目分析

题目显而易见，就是个屑最大公约数，其实我感觉题解都没必要，不过俺很敬业写一下吧

3.算法实现

看你提交版本了，不过俺只会教cpp的内容，py or其他语言 只能去群里**@社长**他们强迫他们写题解了

1.如果你提交版本在cpp17以上，那么好，你只需要键入头文件<numeric>(俺不确定万能头是否包含，不过应该是有的，因为我在此平台测试过了)

然后，你只需要 int ans= std::gcd(a,b);（如果你写using namespace std；可省略std）

完美解决！

2.如果是更低版本，那就要手打gcd函数了，不过数学逻辑也很简单，a，b的最大公约数等价于较小数和两数相除余数的最大公约数

即(gcd(a, b) = gcd(b, a % b))

那我们只需要不断循环此过程让余数为0即可，剩下的那个自然就是我们所求的了

完美解决！

4.复杂度

1.时间：O(logn)

2.空间：O(1)

二.完整代码

1.cpp17及以上

#include <bits/stdc++.h>

using namespace std;

#define int long long



signed main(){

​    ios::sync_with_stdio(false);

​    cin.tie(0);

​    cout.tie(0);

​    int a,b;

​    cin>>a>>b;

​    int ans = gcd(a,b);

​    cout<<ans<<'\n';

​    return 0;

}

2.cpp17以下

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

int gcd(int a,int b){
    while(b){
        int t = a%b;
        a = b;
        b = t;
    }
    return a;
}

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int a,b;
    cin>>a>>b;
    int ans = gcd(a,b);
    cout<<ans<<'\n';

    return 0;
}

PS：非专业题解！有任何错误记得联系我！！！