最大公约数gcd和最小公倍数lcm

一、相关公式及其性质

文章只服务于竞赛，所以不会涉及证明。

辗转相除法：gcd(a, b) = gcd(b, a % b); 直到 b == 0，就可以知道上一层递归中的 a % b == 0，所以上一层的 b 就是答案，也就是这一层递归的 a

gcd(a, b) * lcm(a, b) = a * b

所以求最小公倍数就是 a * b / gcd(a, b)

二、例题

1、最大公约数

B3736 [信息与未来 2018] 最大公约数 - 洛谷

// https://www.luogu.com.cn/problem/B3736
#include <bits/stdc++.h>
using namespace std;int gcd(int a, int b)
{if(b == 0)return a;return gcd(b, a % b);
}int main()
{int a, b, c;cin >> a >> b >> c;cout << gcd(gcd(a, b), c);return 0;
}

2、小红的 gcd

登录—专业IT笔试面试备考平台_牛客网

// https://ac.nowcoder.com/acm/problem/275615
#include <bits/stdc++.h>
using namespace std;// 数据a实在太大，只能用string存，只要取模一次b就能用ll gcd解决问题
// 所以边读取a边取模b #define ll long longll ch(string s, ll b)
{ll tmp = 0;for(auto x : s){tmp = tmp * 10 + (x - '0');tmp %= b;}return tmp;
}ll gcd(ll a, ll b)
{if(b == 0)return a;return gcd(b, a % b);
}int main()
{string a;ll b;cin >> a >> b;ll tmp = ch(a, b);cout << gcd(tmp, b);return 0;
}

如果一个十进制的数太大太大，只能用 string 存，而要想得到这个数，操作就是 *10 + 对应数字