小白学Fibonacci之一

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

一天,Z懂得了Fibonacci数列,发现数列有以下规律:
F[1]=F[2]=1; F[N]=F[N-1]+F[N-2];
于是Z觉得很神奇,想知道任意两个Fibonacci数有没有大于1的公约数。但是光在有限的范围内手算还不行,于是Z找到了你,希望你能帮忙编个程序算算。
任务:指定两个Fibonacci数的项数(也就是这两个数各是第几项),求出这两个数的最大公约数。
例如输入3 6,输出2(因为GCD(F[3],F[6])=2)。

Input

多组数据,每行两个数A,B。到文件末尾。
 0<A,B<100007

Output

每组数据输出一行。保证最后结果不超过2^64-1,所以使用64位无符号整数。

Sample Input

30 15
14 28
12 24
17 17
30 6
24 24
20 10
24 12
29 29
9 18

Sample Output

610
377
144
1597
8
46368
55
144
514229
34

Hint

 

Source