872. 最大公约数

题目传送门

一、理解与感悟

性质1:

说明 : d|a 是指d能整除a

下面的性质是存在的,可以记下来:

if d|a && d|b {
    d | (a+b) == true;
    d | (a * x + b * y) == true;
}

性质2:

说明: \((a,b)\) 代表\(a\)和\(b\)的最大公约数
下面的性质是存在的,可以记下来:

(a,b) =(b, a mod b)

原理让李永乐老师的证明一下给你看: https://v.qq.com/x/cover/0ekhxvyhbdh4h7u/n09564m4hsw.html

二、C++ 代码

#include <bits/stdc++.h>

using namespace std;

// 辗转相除法,求最大公约数
// 欧几里得算法
// 视频讲解原理:https://haokan.baidu.com/v?vid=2565318146747981528&pd=bjh&fr=bjhauthor&type=video
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main() {
    //优化读入
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    while (n--) {
        int a, b;
        cin >> a >> b;
        printf("%d\n", gcd(a, b));
    }
    return 0;
}
上一篇:[2021 CCCC天梯赛] 可怜的简单题 (概率期望 莫比乌斯反演 杜教筛)


下一篇:牛客数字染色莫比乌斯容斥