給你 n,m, 求 gcd(Fm,Fn)

*Fx 代表 Fibonacci 數列第 x 項

2019/6/8 時限調降至 0.5s

輸入說明
輸入有多行

每行有 m,n 兩數(m,n<=10000)

輸出說明
答案(保證可以用 unsigned long long 存)


1. 此題的考點在於如何使用遞迴函數來運算 fibonacci 數列
2. 但使用此解法無法通過測支, 所以需優化程式, 查表法為最速解
3. 先使用另一個.py 列印出 1~94 的 fibonacci 數列 list
4. 此題須了解到兩 fibonacci 數做 GCD 的結果 = 兩數做 GCD 的 fibonacci 數

1
2
3
4
5
6
7
8
# 使用偷吃步預測 fibonacci 數列只會遞迴至 94 項, 優先使用 list 查表法降低處理時間, 如使用遞迴法書寫 fibonacci 數列, 有機會溢出, 故使用 list 法
def fibonacci(x):
    for i in range(2,x+1,1):
        fibon_list.append(fibon_list[-1]+fibon_list[-2])

fibon_list=[0,1]
fibonacci(94)
print(fibon_list)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def gcd(a,b):
    r=1
    while r!=0:
        r=a%b
        a=b
        b=r
    return a

fibon_list=[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377
            , 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657
            , 46368, 75025, 121393, 196418, 317811, 514229, 832040
            , 1346269, 2178309, 3524578, 5702887, 9227465, 14930352
            , 24157817, 39088169, 63245986, 102334155, 165580141
            , 267914296, 433494437, 701408733, 1134903170
            , 1836311903, 2971215073, 4807526976, 7778742049
            , 12586269025, 20365011074, 32951280099, 53316291173
            , 86267571272, 139583862445, 225851433717, 365435296162
            , 591286729879, 956722026041, 1548008755920
            , 2504730781961, 4052739537881, 6557470319842
            , 10610209857723, 17167680177565, 27777890035288
            , 44945570212853, 72723460248141, 117669030460994
            , 190392490709135, 308061521170129, 498454011879264
            , 806515533049393, 1304969544928657, 2111485077978050
            , 3416454622906707, 5527939700884757, 8944394323791464
            , 14472334024676221, 23416728348467685
            , 37889062373143906, 61305790721611591
            , 99194853094755497, 160500643816367088
            , 259695496911122585, 420196140727489673
            , 679891637638612258, 1100087778366101931
            , 1779979416004714189, 2880067194370816120
            , 4660046610375530309, 7540113804746346429
            , 12200160415121876738, 19740274219868223167
            , 31940434634990099905]

while True:
    try:
        first,second=map(int,input().split())        
        ans=gcd(first,second)# 先做 GCD
        print(fibon_list[ans])# 查表 GCD 對應的 fibonacci 數
    except:
        break


e272. gcd(Fm,Fn)



作者: 微風