#23499: (python)為什麼TLE(已經使用輾轉相除法了)


CHUCHUCHU (unknown)

學校 : 國立清華大學
編號 : 138021
來源 : [140.114.96.81]
最後登入時間 :
2020-12-02 14:21:09
a024. 最大公因數(GCD) | From: [140.114.96.81] | 發表日期 : 2020-11-23 17:14

x,y=map(int,input().split())


def test(x,y):

    while  0<x<2**31 and 0<y<2**31:

        if x>y:

            x=x-y

        elif y>x:

            y=y-x

        elif x==y:

            x=y-x

            y=y    

    if x==0:

        return y

    elif y==0:

        return x

    

print(test(x,y))

 
#23500: Re:(python)為什麼TLE(已經使用輾轉相除法了)


snakeneedy (蛇~Snake)

學校 : 國立高雄師範大學附屬高級中學
編號 : 7661
來源 : [114.40.8.251]
最後登入時間 :
2023-01-25 19:16:06
a024. 最大公因數(GCD) | From: [123.194.188.217] | 發表日期 : 2020-11-23 18:04

問題應該就出在你寫的輾轉相除法不夠有效率,可以試試看用餘數運算子 % 來處理。以兩正整數 x y 來說

while x >= y:
    x -= y

可以精簡成

x %= y

再善用輾轉相除法的交換式 ,可以讓程式寫得更精簡,尤其 Python 的 swap 可以寫得很簡單

a, b = b, (a % b)
 
ZeroJudge Forum