P2152 [SDOI2009]SuperGCD 题解

题目大意

高精度 (GCD)

P2152 [SDOI2009]SuperGCD

问题求解

在看排水问题时，我去研究了除法 (GCD) 的问题，发现有一个叫辗转相减法的东西，大概就是这个样子

[1]. 若 (a) 为奇数，(b) 为偶数，(GCD(a,b)=GCD(a,b/2))

[2]. 若 (a) 为偶数，(b) 为奇数，(GCD(a,b)=GCD(a/2,b))

[3]. 若 (a) 为偶数，(b) 为偶数，(GCD(a,b)=2GCD(a/2,b/2))

[4]. 若 (a) 为奇数，(b) 为奇数，(GCD(a,b)=GCD(a-b,b)(a>b))

其实和辗转相除法差不多，就是把除换成减

代码实现

至于我的代码懒得写了

import fractions
print(fractions.gcd(int(input()),int(input())))