首页 > 试题广场 >

复杂的最大公约数

[编程题]复杂的最大公约数
  • 热度指数:61 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定两个正整数 a,b,记区间 \left[a,b\right] 中的所有整数依次为 a,a+1,a+2,\dots,b。求一个最大的正整数 d,使得区间内的每一个整数都能够被 d 整除。
\hspace{15pt}需要特别注意,输入中的 a,b 的数值可能高达 10^{100},远远超过常见的 64 位整数范围。

【名词解释】
\hspace{23pt}\bullet\,最大公约数\gcd):对于两个正整数 x,y,最大的正整数 d 满足 d\mid xd\mid y,称 dxy 的最大公约数,记为 \gcd\left(x,y\right)

输入描述:
\hspace{15pt}在一行上输入两个整数 a,b\left(1\leqq a\leqq b\leqq 10^{100}\right)


输出描述:
\hspace{15pt}输出一个整数,表示区间 \left[a,b\right] 内所有整数的最大公约数。
示例1

输入

1 2

输出

1

说明

整数 12 的最大公约数为 1,因此答案为 1
示例2

输入

1145141919810 1145141919810

输出

1145141919810
#include <iostream>
using namespace std;

int main() {
    string s1,s2;
    cin>>s1;
    cin>>s2;
    if(s1!=s2) cout<<1;
    else cout<<s1;
    return 0;
}
// 64 位输出请用 printf("%lld")
发表于 2025-07-06 11:01:12 回复(0)