NC200091. The GCD of Fibonacci Numbers
描述
The Fibonacci sequence is the sequence of numbers such that every element is equal to the sum of the two previous elements, except for the first two elements f0 and f1 which are respectively zero and one. The first few numbers in the Recaman's Sequence is 0,1,1,2,3,5,8,... The ith Fibonacci number is denoted fi.
The largest integer that divides both of two integers is called the greatest common divisor of these integers. The greatest common divisor of a and b is denoted by gcd(a,b).
Two positive integers m and n are given,you must compute the GCD(fm,fn).
输入描述
The first linecontains one integer T（T ≤ 100）,the number of test cases.
For each test case,there are two positive integers m and n in one line. (1 ≤m,n ≤ 231 , GCD(m,n) ≤ 45)
输出描述
Foreach the case, your program will outputthe GCD(fm,fn).
示例1
输入:
4 1 2 2 3 2 4 3 6
输出:
1 1 1 2
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 352K, 提交时间: 2020-02-21 19:07:50
#include<bits/stdc++.h>
using namespace std;
long long f[60];
int main()
{
f[1]=1,f[2]=1;
for(int i=3;i<=50;i++)
f[i]=f[i-1]+f[i-2];
int T;
cin>>T;
while(T--)
{
int n,m;
cin>>m>>n;
cout<<f[__gcd(n,m)]<<endl;
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 6ms, 内存消耗: 412K, 提交时间: 2020-01-11 20:57:19
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long f[47]={0,1,1,2,3};
int i,n,m,t;
for(i=5;i<47;i++)f[i]=f[i-1]+f[i-2];
cin>>t;
while(t--){
cin>>n>>m;
printf("%d\n",f[__gcd(n,m)]);
}
return 0;
}
pypy3(pypy3.6.1) 解法, 执行用时: 52ms, 内存消耗: 18636K, 提交时间: 2020-01-11 13:05:51
from math import gcd
a = [0, 1]
for i in range(100):
a.append(a[-1] + a[-2])
T = int(input())
for cas in range(T):
n, m = map(int, input().split())
print(a[gcd(n, m)])
Python3(3.5.2) 解法, 执行用时: 29ms, 内存消耗: 3320K, 提交时间: 2020-01-11 12:13:07
import math
for _ in range(int(input())):
n,m=map(int,input().split())
x=0;y=1
for __ in range(math.gcd(n,m)):x,y=y,x+y
print(x)