最大公约数（GCD）和最小公倍数（LCM）是数论的基础概念，在分数约分、比例简化、周期性任务调度、密码学等领域有重要应用。最大公约数与最小公倍数计算器使用经典的欧几里得算法（辗转相除法）计算 GCD，并通过公式快速计算 LCM，支持多个数字的批量计算和详细的计算过程展示。

本案例基于 Kotlin Multiplatform（KMP）与 OpenHarmony，实现了一个最大公约数与最小公倍数计算器：

• GCD 计算：使用欧几里得算法（辗转相除法），时间复杂度 O(log min(a,b))
• LCM 计算：通过公式 LCM(a,b) = (a×b)/GCD(a,b) 计算，避免大数溢出
• 多数字支持：支持两个或多个数字的 GCD/LCM 批量计算
• 过程展示：展示欧几里得算法的每一步计算过程
• 质因数分析：通过质因数分解对比，直观理解 GCD 的含义

---

一、问题背景与典型场景

典型场景：

1. 分数约分：将分数化为最简形式，需要计算分子分母的最大公约数
2. 比例简化：简化比例关系，如 48:18 简化为 8:3
3. 周期性任务调度：计算多个任务的公共执行周期（LCM）
4. 密码学：RSA 算法中计算模逆、扩展欧几里得算法等
5. 编码理论：错误检测和纠正码的设计
6. 算法优化：某些算法中利用 GCD 性质进行优化

优势：

• 算法高效：欧几里得算法时间复杂度为 O(log min(a,b))，非常高效
• 理论基础扎实：欧几里得算法有 2300 多年的历史，理论成熟
• 实用性强：在数学、计算机科学的多个领域有广泛应用
• 关系明确：GCD 和 LCM 之间满足 a×b = GCD(a,b)×LCM(a,b)

---

二、最大公约数（GCD）原理

2.1 基本概念

最大公约数（Greatest Common Divisor, GCD）是指能够同时整除两个或多个整数的最大正整数。

例如：

• GCD(48, 18) = 6
• GCD(12, 18, 24) = 6

性质：

1. GCD(a, b) = GCD(b, a)（交换律）
2. GCD(a, b) = GCD(a, b - a) = GCD(a, b % a)（递推关系）
3. 如果 a > b，则 GCD(a, b) = GCD(b, a % b)
4. GCD(a, 0) = a（基准情况）

2.2 欧几里得算法（辗转相除法）

欧几里得算法是计算 GCD 的经典算法，基于以下数学原理：

核心思想：GCD(a, b) = GCD(b, a mod b)

算法步骤：

1. 如果 b = 0，则 GCD = a
2. 否则，计算 r = a mod b
3. 递归或迭代计算 GCD(b, r)

示例：计算 GCD(48, 18)

步骤 1: 48 = 18 × 2 + 12  →  GCD(48, 18) = GCD(18, 12)
步骤 2: 18 = 12 × 1 + 6   →  GCD(18, 12) = GCD(12, 6)
步骤 3: 12 = 6 × 2 + 0    →  GCD(12, 6) = GCD(6, 0) = 6
结果: GCD(48, 18) = 6

时间复杂度：O(log min(a, b))

证明：每次迭代，较大的数至少减少一半（因为余数小于除数），所以最多需要 log(min(a,b)) 次迭代。

---

三、最小公倍数（LCM）原理

3.1 基本概念

最小公倍数（Least Common Multiple, LCM）是指能够同时被两个或多个整数整除的最小正整数。

例如：

• LCM(48, 18) = 144
• LCM(12, 18, 24) = 72

3.2 LCM 与 GCD 的关系

重要公式：对于两个正整数 a 和 b：

LCM(a, b) = (a × b) / GCD(a, b)

证明思路：

• 设 d = GCD(a, b)，则 a = d × a’, b = d × b’，其中 GCD(a’, b’) = 1
• 显然，LCM(a, b) = d × a’ × b’
• 而 a × b = d × a’ × d × b’ = d² × a’ × b’
• 因此，(a × b) / d = d × a’ × b’ = LCM(a, b)

示例：计算 LCM(48, 18)

GCD(48, 18) = 6
LCM(48, 18) = (48 × 18) / 6 = 864 / 6 = 144

3.3 多个数的 LCM

对于多个数 a₁, a₂, …, aₙ，可以通过递归计算：

LCM(a₁, a₂, ..., aₙ) = LCM(LCM(a₁, a₂), a₃, ..., aₙ)

示例：计算 LCM(12, 18, 24)

步骤 1: LCM(12, 18) = (12 × 18) / GCD(12, 18) = 216 / 6 = 36
步骤 2: LCM(36, 24) = (36 × 24) / GCD(36, 24) = 864 / 12 = 72
结果: LCM(12, 18, 24) = 72

---

四、Kotlin 实现详解

4.1 欧几里得算法实现

fun gcd(a: Int, b: Int): Int {
    var x = a
    var y = b
    
    while (y != 0) {
        val temp = y
        y = x % y
        x = temp
    }
    
    return x
}

关键点：

• 迭代实现，避免递归栈溢出
• 每次循环交换 x 和 y，使得 x 始终为较大的数
• 当 y = 0 时，x 即为 GCD

4.2 带步骤展示的 GCD 计算

fun gcdWithSteps(a: Int, b: Int): Pair<Int, List<String>> {
    var x = a
    var y = b
    val steps = mutableListOf<String>()
    
    steps.add("开始: GCD($x, $y)")
    
    var stepNum = 1
    while (y != 0) {
        val quotient = x / y
        val remainder = x % y
        steps.add("步骤 $stepNum: $x = $y × $quotient + $remainder")
        val temp = y
        y = remainder
        x = temp
        stepNum++
    }
    
    steps.add("结果: GCD = $x")
    return Pair(x, steps)
}

关键点：

• 记录每一步的除法运算过程
• 展示商和余数，便于理解算法原理

4.3 LCM 计算实现

fun lcm(a: Int, b: Int): Int {
    return if (a == 0 || b == 0) 0 else (a * b) / gcd(a, b)
}

关键点：

• 处理 0 的情况（LCM 为 0）
• 使用公式避免大数溢出（但需要注意 a×b 可能溢出）

4.4 多个数的 GCD/LCM 计算

fun gcdMultiple(nums: List<Int>): Int {
    var result = nums[0]
    for (i in 1 until nums.size) {
        result = gcd(result, nums[i])
    }
    return result
}

fun lcmMultiple(nums: List<Int>): Int {
    var result = nums[0]
    for (i in 1 until nums.size) {
        result = lcm(result, nums[i])
    }
    return result
}

关键点：

• 逐个累积计算，每次计算两个数的 GCD/LCM
• 对于 n 个数，需要 n-1 次两两计算

4.5 质因数分解对比

通过质因数分解可以直观理解 GCD 的含义：

fun primeFactors(n: Int): List<Int> {
    val factors = mutableListOf<Int>()
    var num = n
    var i = 2
    
    while (i * i <= num) {
        while (num % i == 0) {
            factors += i
            num /= i
        }
        i++
    }
    if (num > 1) factors += num
    return factors
}

// 计算公共质因数
val factors1 = primeFactors(a)
val factors2 = primeFactors(b)
val commonFactors = factors1.intersect(factors2.toSet()).toList().sorted()

关键点：

• GCD 等于所有公共质因数的最小次幂的乘积
• 例如：48 = 2⁴ × 3，18 = 2 × 3²，GCD = 2 × 3 = 6

---

五、ArkTS 前端集成

5.1 页面布局设计

采用左右分区布局，蓝色主题：

Row() {
  // 左侧输入区域（45%）
  Column() {
    // 功能介绍
    // 输入区域
    // 快捷按钮
    // 执行按钮
  }
  .width('45%')
  
  // 右侧结果显示区域（55%）
  Column() {
    // 加载指示器
    // 结果展示
  }
  .width('55%')
}

5.2 功能模块

1. 输入区域：

   • TextArea 用于输入数字列表
   • 支持格式：numbers=48,18 或直接输入 48,18
   • 快捷按钮：两数示例、三数示例、清除

2. 执行逻辑：

   private executeCase() {
     this.isLoading = true
     setTimeout(() => {
       try {
         let output: string = gcdAndLcmCalculator(this.inputValue)
         this.result = output
       } catch (error) {
         this.result = `❌ 执行出错: ${error}`
       } finally {
         this.isLoading = false
       }
     }, 100)
   }
   

3. 结果显示：

   • 使用 Scroll 包裹 Text 显示格式化结果
   • 等宽字体（fontFamily('monospace')）保持对齐
   • 展示 GCD 和 LCM 的计算结果、过程步骤、验证信息

5.3 用户交互

• 快捷填充：一键填入常用示例
• 实时反馈：加载状态指示器
• 详细展示：显示计算过程的每一步

---

六、工程化应用

6.1 性能优化

1. 迭代实现：

   • 使用迭代而非递归，避免栈溢出
   • 对于大数，迭代实现更安全

2. 溢出处理：

   • 计算 LCM 时，注意 a×b 可能溢出
   • 可以使用 a / GCD(a,b) * b 来减少溢出风险

3. 大数支持：

   • 可以使用 BigInteger 处理超大数字
   • Kotlin 的 java.math.BigInteger 提供大数运算

6.2 扩展功能

1. 扩展欧几里得算法：

   • 计算 GCD 的同时，求出 x 和 y 使得 ax + by = GCD(a,b)
   • 在密码学中用于计算模逆

2. Stein 算法（二进制 GCD）：

   • 利用位运算加速 GCD 计算
   • 适合计算机实现

3. 分数运算：

   • 基于 GCD/LCM 实现分数的加减乘除
   • 自动约分到最简形式

4. 同余方程求解：

   • 利用 GCD 判断线性同余方程是否有解
   • 中国剩余定理的应用

6.3 实际应用场景

1. 分数约分：

   fun simplifyFraction(numerator: Int, denominator: Int): Pair<Int, Int> {
       val g = gcd(numerator, denominator)
       return Pair(numerator / g, denominator / g)
   }
   

2. 周期性任务调度：

   • 计算多个任务的公共执行周期
   • 例如：任务 A 每 3 天执行，任务 B 每 4 天执行，公共周期为 LCM(3, 4) = 12 天

3. 比例简化：

   • 简化比例关系
   • 例如：48:18 简化为 8:3（除以 GCD(48, 18) = 6）

4. 密码学应用：

   • RSA 算法中计算密钥
   • 扩展欧几里得算法计算模逆

5. 编码理论：

   • 错误检测码的设计
   • 循环冗余校验（CRC）算法

6. 算法优化：

   • 某些动态规划问题中利用 GCD 性质
   • 图论中计算路径周期

---

七、算法复杂度分析

7.1 时间复杂度

欧几里得算法：

• 最坏情况：O(log min(a, b))
• 平均情况：O(log min(a, b))
• 最好情况：O(1)（当 a 是 b 的倍数时）

证明：

• 每次迭代，较大的数至少减少一半
• 设 a > b，经过一次迭代后得到 (b, a mod b)
• 如果 a mod b ≤ b/2，则下次迭代的较大数 ≤ b/2
• 如果 a mod b > b/2，则 a = b×q + r，其中 r > b/2，所以 a ≥ b + r > 3b/2
• 因此，每两次迭代，较大的数至少减少到原来的 2/3
• 所以总迭代次数为 O(log min(a, b))

7.2 空间复杂度

• 迭代实现：O(1)
• 递归实现：O(log min(a, b))（递归栈深度）

7.3 多个数的复杂度

对于 n 个数：

• GCD：O(n × log min(max(nums)))
• LCM：O(n × log min(max(nums)))

---

八、总结

最大公约数与最小公倍数计算器展示了：

• 经典算法：欧几里得算法是数论与算法教学的经典案例，有 2300 多年历史
• 高效实现：O(log min(a,b)) 的时间复杂度，对于大数也非常高效
• 实用价值：在分数运算、任务调度、密码学等领域有重要应用
• 关系明确：GCD 和 LCM 之间满足 a×b = GCD×LCM，这是数论的基本定理

通过 KMP 与 OpenHarmony 的集成，实现了跨平台的 GCD/LCM 计算工具，可用于教学演示、算法研究以及实际应用开发。

---

相关技术栈：

• Kotlin Multiplatform（KMP）
• OpenHarmony / ArkTS
• 欧几里得算法（辗转相除法）
• 质因数分解
• 数论基础

应用领域：

• 分数运算
• 周期性任务调度
• 密码学
• 编码理论
• 算法优化

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.csdn.net