CF664A Complicated GCD

2019-08-02 15:47:42


这是道数论题~

题面描述:

给出 $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$ ):

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)

最后来个小广告:我的博客

里面会教你PPT,教你做博客,教你A水题~