TB椰程 TypeBuddy 打字搭子

最大公约数

CSP-J · 编程模板 · 代码 · cpp · 难度 2/5 · 共 310 字

gcd(a,b) = gcd(b,a 模 b)，除到余数为 0

  • gcd
  • 辗转相除

前置内容

正文

// ── 辗转相除求最大公约数 ──
// 欧几里得算法
// 原理：gcd(a, b) = gcd(b, a mod b)
int gcd(int a, int b) {
    // b 变成 0 时，a 就是答案
    while (b != 0) {
        // 余数小于除数，规模在缩小
        int t = a % b;
        // 除数成为新的被除数
        a = b;
        // 余数成为新的除数
        b = t;
    }
    return a;
}
// 最小公倍数 lcm = a / gcd * b
// 先除后乘防溢出

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK