首页 > 试题广场 >

复杂的最大公约数

[编程题]复杂的最大公约数
  • 热度指数：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 x 且 d\mid y，称 d 为 x 与 y 的最大公约数，记为 \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

说明

整数 1 与 2 的最大公约数为 1，因此答案为 1。
示例2

输入

1145141919810 1145141919810

输出

1145141919810
算法知识视频讲解
添加回答
C++
牛客207135092号头像 牛客207135092号
#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)
提交观点

问题信息

难度：
1条回答 28浏览

热门推荐

相关试题

复杂的最大公约数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号