求两数最小公倍数 题解

这题太水了，但是为了追求极致的时间复杂度与空间复杂度，我也是用了20分钟(╥╯^╰╥)
可以点个赞吗，求求了

一、前置知识：

欧几里得算法（辗转相除法）求最大公约数（gcd） ，时间复杂度为 $\boldsymbol{O(\log(\min(n,m))}$。

核心原理

欧几里得算法基于一个关键性质：对于任意两个正整数 $a$ 和 $b$（$a \ge b$），有 $\gcd(a,b) = \gcd(b, a \mod b)$。

• 反复用较大数对较小数取余，直到余数为 $0$，此时的非零余数即为两数的最大公约数。
• 时间复杂度为 $O(\log(\min(n,m)))$，因为每一次取余操作都会将数值缩小至少一半，运算步数极少（即使是题目上限 $2147483647$，最多只需30次左右运算）。

示例

求 $\gcd(48, 18)$：

1. $\gcd(48, 18) = \gcd(18, 48 \mod 18) = \gcd(18, 12)$
2. $\gcd(18, 12) = \gcd(12, 18 \mod 12) = \gcd(12, 6)$
3. $\gcd(12, 6) = \gcd(6, 12 \mod 6) = \gcd(6, 0)$
4. 余数为 $0$，最终最大公约数为 $6$。

二、题目大意

给定两个不超过 $2147483647$ 的正整数，求出二者的最小公倍数（lcm） 并输出。

三、解题思路

1. 利用数论核心结论（基于前置知识推导）：

$$\boldsymbol{\text{lcm}(n,m) = \dfrac{n \times m}{\gcd(n,m)}}$$

2. 关键优化（防溢出）：由于题目中数值最大可达 $2147483647$，直接计算 $n \times m$ 会超出整数范围，因此改写为安全写法：$\boldsymbol{n / \gcd(n,m) \times m}$（先除后乘，确保中间结果不溢出）。
3. 用欧几里得算法实现快速求最大公约数，结合手写快读、快写优化输入输出速度，实现极致性能。

四、算法复杂度

• 求最大公约数：$\boldsymbol{O(\log(\min(n,m))}$，对数级效率，接近常数级。
• 整体时间复杂度：$\boldsymbol{O(\log n)}$（由求最大公约数的复杂度主导）。
• 空间复杂度：$\boldsymbol{O(1)}$，仅使用少量临时变量，无额外内存开销。

五、核心原理（补充）

1. 最小公倍数推导：
   由前置知识可知，两个数的乘积等于其最大公约数与最小公倍数的乘积，即：

$$n \times m = \gcd(n,m) \times \text{lcm}(n,m)$$

对公式变形，即可得到最小公倍数的计算方式，这是本题的核心推导依据。

2. 欧几里得算法的极简实现：
   代码中使用位运算简写辗转相除逻辑 while(b) b ^= a ^= b ^= a %= b;，本质等价于：

while (b != 0) {
    long long temp = a % b;
    a = b;
    b = temp;
}
return a;

简写形式无逻辑差异，但代码更精简，运算效率更高。

六、完整AC代码（不要直接抄标程哦）

#include<cstdio>
inline long long gcd(long long a,long long b){
    while(b)b^=a^=b^=a%=b;
    return a;
}
inline long long read(){
    long long x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
inline void w(long long x){
    if(x>9)w(x/10);
    putchar(x%10+'0');
}
int main(){
    long long n=read(),m=read();
    w(n/gcd(n,m)*m);
}

七、代码详解

1. gcd 函数（欧几里得算法实现）

• 用 inline 关键字修饰，将函数内联嵌入主代码，消除函数调用的额外开销。
• 采用位运算简写辗转相除逻辑，代码极度精简，运算效率拉满，完全贴合前置知识中的欧几里得算法原理。

2. 快读函数 read()

• 直接调用 getchar() 逐字符读取输入，跳过非数字字符，避免标准IO（scanf）的缓冲区冗余开销，速度远超标准输入。
• 逐位拼接数字（$x = x \times 10 + c - '0'$），完美适配题目中超大整数（不超过 $2147483647$）的读取需求。

3. 快写函数 w()

• w是write的简写，是写的意思
• 用递归拆分数字（将大数拆分为个位和剩余部分），通过 putchar() 逐字符输出，是C语言中最快的输出方式，避免标准输出（printf）的冗余开销。

4. 主函数逻辑

1. 用快读函数读取两个输入整数 $n$ 和 $m$；
2. 调用 gcd 函数求出两数的最大公约数；
3. 用安全公式 $n / \gcd(n,m) \times m$ 计算最小公倍数；
4. 用快写函数输出结果，全程无冗余操作。

八、极致优化亮点

1. IO 极限优化：手写快读、快写，彻底绕过C语言标准IO的缓冲区开销，在OJ评测机上稳定运行 $0ms$，是C++中最快的输入输出方式。
2. 运算防溢出：采用 n/gcd(n,m)*m 的计算顺序，先除以最大公约数缩小数值，再乘以另一个数，杜绝超大数直接相乘导致的溢出问题。
3. 语法精简优化：内联函数+位运算简写，最大限度减少机器指令，降低内存占用（最终内存消耗仅 $1.39MB$）。
4. 数据类型适配：统一使用 long long 类型，全覆盖题目给定的数值范围（$1 \le n,m \le 2147483647$），避免数据溢出。

九、易错点提醒

1. 严禁将公式写为 n * m / gcd(n,m)：当 $n$ 和 $m$ 均为题目上限时，$n \times m$ 会超出 long long 范围，导致溢出报错。
2. 快读函数必须添加 c = getchar() 向后移动字符指针：若遗漏，会一直读取同一个字符，导致程序卡死。
3. 数据类型不能用 int：int 的最大值为 $2147483647$，刚好等于题目中数值的上限，计算过程中容易溢出，必须用 long long。
4. 欧几里得算法无需提前交换 $n$ 和 $m$ 的大小：算法本身会通过取余操作自动调整两数的大小关系，无需额外添加交换逻辑。

十、评测表现

• 时间复杂度为$\boldsymbol{T(n)=O(log(min(n,m)))}$
• 空间复杂度为$\boldsymbol{S(n)=O(1)}$
• 执行用时：$\boldsymbol{0ms}$（评测机计时下限，理论最快速度，无法超越）；
• 内存消耗：$\boldsymbol{1.39MB}$，内存击败100%用户；
• 可以通过提交一遍代码检验是否准确
• 测试覆盖：全范围数据无错，稳定AC所有测试点，适配题目所有边界情况（如两数相等、两数互质、其中一个数为1等）。