一、理解与感悟
性质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;
}