7134: 最大公约数之更相减损术 分享至QQ空间

Time Limit(Common/Java):1000MS/4000MS     Memory Limit:65536KByte
Total Submit: 151            Accepted:89

Description

《九章算术》是中国古代的数学专著,其中的“更相减损术”可以用来求两个数的最大公约数,其文言文描述为“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。”

翻译为现代语言如下:

1)任意给定两个正整数,判断它们是否都是偶数。若是,用2约简;若不是,执行 步骤 2);

2)以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数。

请你根据这个方法求出数A和B的最大公约数。

Input

输入共两行,第一行一个正整数 A,第二行一个正整数 B(1≤A,B≤107)。

Output

在第一行输出一个整数,表示 A,B 的最大公约数。

Sample Input

Sample Output

Hint

程序流程图如下所示

image.png

Source

TZOJ

Uploader

TZOJ


[Submit] [Status]

|Back |   | Top|
Copyright @ 2008-2022(浙ICP备2022001332号), TZOJ. All Rights Reserved.