题解 P2152 【[SDOI2009]SuperGCD】

aiyougege · 2018-05-07 20:24:34 · 题解

[SDOI2009]SuperGCD

Solution

　　其实如果不需要高精度是很好做的, 就是需要注意递归会爆栈(递归层数太多), 需要用循环模拟.这个题提醒我们尽量少写函数和递归

　　因为c++写高精度实在太鬼畜, 所以就用Python水一下.

Code

递归版, 只有40, 和c++一样

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)

a=int(input())
b=int(input())
print(gcd(a,b))

循环版, 100分 Python 语法比较神奇

将s_1,s_2,s_3,\cdots 的值分别赋给a,b,c,\cdots

a=int(input())
b=int(input())

while b:
    a,b=b,a%b

print(a)