题目链接

复杂的最大公约数

题目描述

给定两个正整数 和 ，求区间 中所有整数的最大公约数。即求 。输入中的 和 可能会非常大，超出 64 位整数的范围。

解题思路

本题要求一个连续整数区间的最大公约数。我们可以通过分析最大公约数的性质来简化问题。

设 。根据最大公约数的定义， 必须能够整除区间内的每一个数。

我们分两种情况讨论：

  1. 当 时： 区间内只有一个整数 。根据定义，一个数的最大公约数就是它本身。所以，当 时，答案就是 。

  2. 当 时： 此时，区间 至少包含两个连续的整数： 和 。 因为 是整个区间的最大公约数，所以 必须能同时整除 和 。 根据最大公约数的一条重要性质：如果一个数能同时整除两个整数，那么它也一定能整除这两个整数的差。 因此， 必须能整除 。 唯一能整除 1 的正整数只有 1 本身。所以，在这种情况下， 必定为 1。

综上所述，我们只需要判断 和 是否相等即可。

关于大数处理： 题目提到输入的数值可能非常大。

  • 在 Python 中，整数类型支持任意精度，可以直接处理。
  • 在 Java 中，需要使用 java.math.BigInteger 类来处理。
  • 在 C++ 中，没有内置的大数类型，但由于我们只需要比较两个数是否相等，所以可以将它们作为字符串读入并进行比较，从而避免实现复杂的大数运算。

代码

#include <iostream>
#include <string>

using namespace std;

int main() {
    string a, b;
    cin >> a >> b;

    if (a == b) {
        cout << a << "\n";
    } else {
        cout << 1 << "\n";
    }
    
    return 0;
}

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger a = sc.nextBigInteger();
        BigInteger b = sc.nextBigInteger();

        if (a.equals(b)) {
            System.out.println(a);
        } else {
            System.out.println(1);
        }
    }
}

a, b = map(int, input().split())

if a == b:
    print(a)
else:
    print(1)

算法及复杂度

  • 算法：数学推理与分类讨论
  • 时间复杂度：。主要开销在于读取和比较两个可能很长的数字字符串，其时间复杂度与数字的位数成正比。
  • 空间复杂度：。需要空间来存储输入的两个大数。