最大公约数和最小公倍数
gcd(a,b) 就是求a,b的最大公约数
lcm(a,b) 就是求a,b的最小公倍数
这里讲一个公式： a*b=gcd(a,b)*lcm(a,b)
通过这个公式，我们就可以根据gcd从而求出lcm
至于求gcd的算法 初中就已经介绍过了辗转相除法
LL gcd(LL a,LL b) { LL t; while (b) { t = b; b = a % b; a = t; } return a; }
也可以用递归的写法
LL gcd(LL a,LL b) { if (b==0) return a; else return gcd(b, a%b); }
那么 我们就可以求得 lcm = a * b / gcd(a,b)
当然这种写法可能会爆数据，推荐写成
lcm = a / gcd(a,b) * b;
这里给几个常用的公式：
gcd(ka, kb) = k * gcd(a, b)
lcm(ka, kb) = k * lcm(a, b)
lcm(S/a, S/b) = S/gcd(a, b)
查看16道真题和解析