CF664A Complicated GCD

URL :洛谷

这是道数论题~

题面描述:

给出$a$,$b$,求$a,a+1,a+2……b$的最大公约数

思路:

相邻两个自然数互质,所以如果$a<b$的话,答案就是1,如果$a=b$的话,答案就是$a$~

为什么呢?下面给出相邻两个自然数互质的证明

设小的数为$a$,则大的为$a+1$

假设两数不互质,则有一个大于1的公约数m

$\because$ 有一个大于1的公约数m

$\therefore$ $xm=a,ym=a+1$

$\therefore$ $m(y-x)=1$

$\because$ $m>1,y-x\geq1$

$\therefore$ 矛盾,命题不成立

$\therefore$ 相邻两个自然数互质

但是我们发现$a,b<=10^{100}$所以我们可以使用$Python$自带高精度,如果要使用$C++$的话,就用两个字符串读入数然后逐个比较~

代码($Python$):

1
2
3
4
5
6
7
a,b=input().split()#因为a,b在1行,所以使用split
a=int(a)#转整数
b=int(b)
if a<b:#如果a不等于b,输出1
print(1)
else :#如果a等于b,输出a
print(a)