#P2152. [SDOI2009] SuperGCD

    ID: 1170 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>最大公约数gcd高精度各省省选2009山东O2优化

[SDOI2009] SuperGCD

题目描述

Sheng bill 有着惊人的心算能力,甚至能用大脑计算出两个巨大的数的最大公约数!因此他经常和别人比赛计算最大公约数。有一天Sheng bill很嚣张地找到了你,并要求和你比赛,但是输给 Sheng bill 岂不是很丢脸!所以你决定写一个程序来教训他。

输入格式

共两行,第一行一个整数 aa,第二行一个整数 bb

输出格式

一行,表示 aabb 的最大公约数。

12
54
6

提示

数据规模与约定

  • 对于 20%20\% 的数据,有 0<a,b10180<a,b\le 10^{18}
  • 对于 100%100\% 的数据,有 0<a,b10100000<a,b\le 10^{10000}