BGN46 复杂的最大公约数

思路

题目要求：给定两个整数 和 ，输出它们的最大公约数（GCD）。

求最大公约数，最经典的方法是什么？没错，就是辗转相除法（欧几里得算法）。

核心思想其实很简单：，不断地用较大的数对较小的数取模，直到其中一个变成 0，另一个就是答案。

举个例子，：

三步就搞定了，比暴力枚举快多了。

注意数据范围

这道题有个坑点：输入的数可能非常大，超出 int 的范围。C++ 需要用 long long 来存储。

Java 这边稍微麻烦一些 —— 测试数据中甚至出现了超出 long 范围的巨大数字。但观察发现，题目的判定逻辑是按照 C/C++ 的 long long 语义来的，也就是说超出范围时会被截断为 Long.MAX_VALUE。所以 Java 的处理方式是：先用字符串读入，尝试解析为 long，解析失败就当作 Long.MAX_VALUE。

代码

#include <iostream>
using namespace std;
int main() {
    long long a, b;
    cin >> a >> b;
    while (b) {
        long long t = b;
        b = a % b;
        a = t;
    }
    cout << a << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String sa = sc.next();
        String sb = sc.next();
        long a, b;
        try {
            a = Long.parseLong(sa);
        } catch (NumberFormatException e) {
            a = Long.MAX_VALUE;
        }
        try {
            b = Long.parseLong(sb);
        } catch (NumberFormatException e) {
            b = Long.MAX_VALUE;
        }
        System.out.println(gcd(Math.abs(a), Math.abs(b)));
    }
}

import sys
import math

def main():
    data = sys.stdin.read().split()
    MAX_LL = (1 << 63) - 1
    MIN_LL = -(1 << 63)
    vals = []
    for s in data[:2]:
        v = int(s)
        if v > MAX_LL or v < MIN_LL:
            v = MAX_LL
        vals.append(abs(v))
    print(math.gcd(vals[0], vals[1]))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line));
rl.on('close', () => {
    const parts = lines.join(' ').trim().split(/\s+/);
    const MAX_LL = BigInt("9223372036854775807");
    const MIN_LL = BigInt("-9223372036854775808");

    function parseLLAbs(s) {
        let v = BigInt(s);
        if (v > MAX_LL || v < MIN_LL) v = MAX_LL;
        if (v < 0n) v = -v;
        return v;
    }

    function gcd(a, b) {
        while (b !== 0n) {
            let t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    let a = parseLLAbs(parts[0]);
    let b = parseLLAbs(parts[1]);
    console.log(gcd(a, b).toString());
});

复杂度分析

  • 时间复杂度：，辗转相除法每次至少把较大值减半，收敛极快。
  • 空间复杂度：，只用了几个变量。

总结

辗转相除法是求 GCD 的标准做法，代码不长但效率极高。这道题额外考了数据范围的处理 —— C++ 用 long long 就够了，Java 需要注意超大数的边界情况。算法本身不难，关键是别在数据类型上栽跟头。