BISHI57　最大公因数与最小公倍数¶

简单通过率 50.13%python3样例通过牛客 AC

牛客原题　源码

讲解章节：运算符与位运算、数论基础

一句话

给定 a,b <= 2e9，输出 gcd 和 lcm。

解题思路¶

这题考什么¶

欧几里得算法（辗转相除法）+ 「gcd 与 lcm 的乘积等于原来两数之积」这条恒等式。

欧几里得算法的依据是一条等式：

gcd(a, b) = gcd(b, a mod b)     (b > 0)

因为 a 的任何公因数 d 同时整除 b 与 a - kb，反之亦然，所以 (a, b) 与 (b, a mod b) 这两对数的公因数集合完全相同*，最大值自然也相同。而余数每一步至少减半：b <= a/2 时 a mod b < b <= a/2， b > a/2 时 a mod b = a - b < a/2。数值指数级收缩，很快收敛到 gcd(g, 0) = g。

lcm 则由算术基本定理得来：把 a、b 按质因数写开， gcd 取每个质数的较小指数，lcm 取较大指数，而较小加较大就是两个指数之和，所以

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

即 lcm(a, b) = a * b / gcd(a, b)。这条恒等式只对两个数成立，三个数以上不能照搬（lcm(2,4,6) != 246 / gcd(2,4,6)）。

数据规模与复杂度¶

单组数据，a,b <= 2e9。gcd 是 O(log min(a,b))；最坏情况由 Lamé 定理给出——相邻两个斐波那契数需要的步数最多， 2e9 附近约 45 步，是彻底的常数级。 Python 直接用 math.gcd（标准库的 C 实现），比手写递归快，也不会因为递归层数爆栈。 lcm 最大到 4e18，Python 的 int 任意精度，不必担心。

坑在哪¶

lcm 要写成 a // g * b，先除后乘。写 a * b // g 时， a*b 最大 4e18 已经越过 int64 上界（9.22e18 勉强够，但换成更大范围就爆），养成先除后乘的习惯；Python 虽然不会溢出，但这个写法是通用正解。先除是安全的：g 一定整除 a，// 不会丢精度；
两个数用一个空格隔开输出在同一行；
Python 3.9 的 math.lcm 存在（3.9 新增），但为了展示恒等式这里手写；
a、b 都保证 >= 1，所以 g >= 1，不会出现除以 0。若题目允许 0，math.gcd(0, 0) 返回 0，那时 a // g 会抛异常，需要特判；
a == b 时 g = a、lcm = a，公式照常成立，不必单独分支。

样例复核¶

12 与 8：辗转相除 gcd(12,8) -> gcd(8,4) -> gcd(4,0) = 4， lcm = 12 // 4 * 8 = 3 * 8 = 24，输出 "4 24" ✓。 7 与 13：互质 g = 1，lcm = 7 // 1 * 13 = 91，输出 "1 91" ✓。

数论基础见 80-数论基础。

参考实现¶

solutions/BISHI57.py
import math
import sys

# 只取前两个整数，多余的空白/换行一概忽略
a, b = map(int, sys.stdin.buffer.read().split()[:2])
g = math.gcd(a, b)                                 # 标准库的辗转相除，几十步收敛
sys.stdout.write("%d %d\n" % (g, a // g * b))      # 先除后乘，避免中间量溢出

BISHI57 最大公因数与最小公倍数¶