求两数最小公倍数 题解
这题太水了，但是为了追求极致的时间复杂度与空间复杂度，我也是用了20分钟(╥╯^╰╥)
可以点个赞吗，求求了
一、前置知识：
欧几里得算法（辗转相除法）求最大公约数（gcd） ，时间复杂度为 O(log(min(n,m))\boldsymbol{O(\log(\min(n,m))}O(log(min(n,m))。
核心原理
欧几里得算法基于一个关键性质：对于任意两个正整数 aaa 和 bbb（a≥ba \ge ba≥b），有 gcd(a,b)=gcd(b,amod b)\gcd(a,b) = \gcd(b, a \mod b)gcd(a,b)=gcd(b,amodb)。
* 反复用较大数对较小数取余，直到余数为 000，此时的非零余数即为两数的最大公约数。
* 时间复杂度为 O(log(min(n,m)))O(\log(\min(n,m)))O(log(min(n,m)))，因为每一次取余操作都会将数值缩小至少一半，运算步数极少（即使是题目上限 214748364721474836472147483647，最多只需30次左右运算）。
示例
求 gcd(48,18)\gcd(48, 18)gcd(48,18)：
1. gcd(48,18)=gcd(18,48mod 18)=gcd(18,12)\gcd(48, 18) = \gcd(18, 48 \mod 18) = \gcd(18, 12)gcd(48,18)=gcd(18,48mod18)=gcd(18,12)
2. gcd(18,12)=gcd(12,18mod 12)=gcd(12,6)\gcd(18, 12) = \gcd(12, 18 \mod 12) = \gcd(12, 6)gcd(18,12)=gcd(12,18mod12)=gcd(12,6)
3. gcd(12,6)=gcd(6,12mod 6)=gcd(6,0)\gcd(12, 6) = \gcd(6, 12 \mod 6) = \gcd(6, 0)gcd(12,6)=gcd(6,12mod6)=gcd(6,0)
4. 余数为 000，最终最大公约数为 666。
二、题目大意
给定两个不超过 214748364721474836472147483647 的正整数，求出二者的最小公倍数（lcm） 并输出。
三、解题思路
1. 利用数论核心结论（基于前置知识推导）：
lcm(n,m)=n×mgcd(n,m)\boldsymbol{\text{lcm}(n,m) = \dfrac{n \times m}{\gcd(n,m)}} lcm(n,m)=gcd(n,m)n×m
2. 关键优化（防溢出）：由于题目中数值最大可达 214748364721474836472147483647，直接计算 n×mn \times mn×m 会超出整数范围，因此改写为安全写法：n/gcd(n,m)×m\boldsymbol{n / \gcd(n,m) \times m}n/gcd(n,m)×m（先除后乘，确保中间结果不溢出）。
3. 用欧几里得算法实现快速求最大公约数，结合手写快读、快写优化输入输出速度，实现极致性能。
四、算法复杂度
* 求最大公约数：O(log(min(n,m))\boldsymbol{O(\log(\min(n,m))}O(log(min(n,m))，对数级效率，接近常数级。
* 整体时间复杂度：O(logn)\boldsymbol{O(\log n)}O(logn)（由求最大公约数的复杂度主导）。
* 空间复杂度：O(1)\boldsymbol{O(1)}O(1)，仅使用少量临时变量，无额外内存开销。
五、核心原理（补充）
1. 最小公倍数推导：
由前置知识可知，两个数的乘积等于其最大公约数与最小公倍数的乘积，即：
n×m=gcd(n,m)×lcm(n,m)n \times m = \gcd(n,m) \times \text{lcm}(n,m) n×m=gcd(n,m)×lcm(n,m)
对公式变形，即可得到最小公倍数的计算方式，这是本题的核心推导依据。
2. 欧几里得算法的极简实现：
代码中使用位运算简写辗转相除逻辑 while(b) b ^= a ^= b ^= a %= b;，本质等价于：
简写形式无逻辑差异，但代码更精简，运算效率更高。
六、完整AC代码（不要直接抄标程哦）
七、代码详解
1. GCD 函数（欧几里得算法实现）
* 用 inline 关键字修饰，将函数内联嵌入主代码，消除函数调用的额外开销。
* 采用位运算简写辗转相除逻辑，代码极度精简，运算效率拉满，完全贴合前置知识中的欧几里得算法原理。
2. 快读函数 READ()
* 直接调用 getchar() 逐字符读取输入，跳过非数字字符，避免标准IO（scanf）的缓冲区冗余开销，速度远超标准输入。
* 逐位拼接数字（x=x×10+c−′0′x = x \times 10 + c - '0'x=x×10+c−′0′），完美适配题目中超大整数（不超过 214748364721474836472147483647）的读取需求。
3. 快写函数 W()
* w是write的简写，是写的意思
* 用递归拆分数字（将大数拆分为个位和剩余部分），通过 putchar() 逐字符输出，是C语言中最快的输出方式，避免标准输出（printf）的冗余开销。
4. 主函数逻辑
1. 用快读函数读取两个输入整数 nnn 和 mmm；
2. 调用 gcd 函数求出两数的最大公约数；
3. 用安全公式 n/gcd(n,m)×mn / \gcd(n,m) \times mn/gcd(n,m)×m 计算最小公倍数；
4. 用快写函数输出结果，全程无冗余操作。
八、极致优化亮点
1. IO 极限优化：手写快读、快写，彻底绕过C语言标准IO的缓冲区开销，在OJ评测机上稳定运行 0ms0ms0ms，是C++中最快的输入输出方式。
2. 运算防溢出：采用 n/gcd(n,m)*m 的计算顺序，先除以最大公约数缩小数值，再乘以另一个数，杜绝超大数直接相乘导致的溢出问题。
3. 语法精简优化：内联函数+位运算简写，最大限度减少机器指令，降低内存占用（最终内存消耗仅 1.39MB1.39MB1.39MB）。
4. 数据类型适配：统一使用 long long 类型，全覆盖题目给定的数值范围（1≤n,m≤21474836471 \le n,m \le 21474836471≤n,m≤2147483647），避免数据溢出。
九、易错点提醒
1. 严禁将公式写为 n * m / gcd(n,m)：当 nnn 和 mmm 均为题目上限时，n×mn \times mn×m 会超出 long long 范围，导致溢出报错。
2. 快读函数必须添加 c = getchar() 向后移动字符指针：若遗漏，会一直读取同一个字符，导致程序卡死。
3. 数据类型不能用 int：int 的最大值为 214748364721474836472147483647，刚好等于题目中数值的上限，计算过程中容易溢出，必须用 long long。
4. 欧几里得算法无需提前交换 nnn 和 mmm 的大小：算法本身会通过取余操作自动调整两数的大小关系，无需额外添加交换逻辑。
十、评测表现
* 时间复杂度为T(n)=O(log(min(n,m)))\boldsymbol{T(n)=O(log(min(n,m)))}T(n)=O(log(min(n,m)))
* 空间复杂度为S(n)=O(1)\boldsymbol{S(n)=O(1)}S(n)=O(1)
* 执行用时：0ms\boldsymbol{0ms}0ms（评测机计时下限，理论最快速度，无法超越）；
* 内存消耗：1.39MB\boldsymbol{1.39MB}1.39MB，内存击败100%用户；
* 可以通过提交一遍代码检验是否准确
* 测试覆盖：全范围数据无错，稳定AC所有测试点，适配题目所有边界情况（如两数相等、两数互质、其中一个数为1等）。
