[luoguP1029] 最大公约数和最小公倍数问题（数论）

传送门

一.暴力枚举（加了点优化）

#include <cstdio> int x, y, ans; inline int gcd(int x, int y) inline int lcm(int x, int y) int main()

二.降维

通过关系式

• x * y == gcd(x, y) * lcm(x, y)

可以枚举 x，根据等式求 y

#include <cstdio> int x, y, ans; inline int gcd(int x, int y) inline int lcm(int x, int y) int main() printf("%d\n", ans); return 0; }

上一篇：差分约束系统总结（转）

下一篇：[luoguP1316] 丢瓶盖（二分答案）

---

数论