題干：
?

我們這樣定義斐波那契數(shù)列，F[1]=1,F[2]=1，當(dāng)n>2時(shí)F[n]=F[n-1]+F[n-2]。

斐波那契數(shù)列的前10項(xiàng)為：1,1,2,3,5,8,13,21,34,55。

歐幾里得算法求解兩個(gè)數(shù)的最大公約數(shù)。我們記gcd(a,b)為整數(shù)a與b的最大公約數(shù)。

當(dāng)b=0時(shí)，gcd(a,0)=a，否則gcd(a,b)=gcd(b,a%b)。其中%為取余運(yùn)算。

在算法設(shè)計(jì)中，求解兩個(gè)數(shù)字公約數(shù)的函數(shù)往往使用遞歸進(jìn)行運(yùn)算。

?

我們現(xiàn)在定義count(a,b)為a,b兩個(gè)整數(shù)在使用歐幾里得算法求解最大公因數(shù)時(shí)的遞歸次數(shù)。

?

例如count(4,8)=3，運(yùn)算過(guò)程如下：

第一次調(diào)用gcd函數(shù)時(shí)進(jìn)入gcd(4,8)，參數(shù)b不為0，所以遞歸進(jìn)入gcd(8,4)。

進(jìn)入gcd(8,4)為函數(shù)的第二次調(diào)用，參數(shù)b不為0，所以遞歸進(jìn)入gcd(4,0)。

進(jìn)入gcd(4,0)為函數(shù)的第三次調(diào)用，參數(shù)b=0。所以遞歸達(dá)到終點(diǎn)，停止遞歸。

在運(yùn)算gcd(8,4)時(shí)共計(jì)進(jìn)行了3次運(yùn)算，所以count(8,4)=3。

現(xiàn)在給定一個(gè)正整數(shù)x，小w想要知道count(F(x),F(x+1))的值，你能告訴他么？

輸入描述:

第一行輸入一個(gè)正整數(shù)T(T≤1000)，表示有T組數(shù)據(jù)。 接下來(lái)T行，每行輸入一個(gè)正整數(shù)x(1≤x≤1000000000)。

輸出描述:

對(duì)于每組數(shù)據(jù)，依次輸出一行一個(gè)正整數(shù)表示count(F(x),F(x+1))

?

示例1

輸入

復(fù)制

4 2 3 4 5

輸出

復(fù)制

3 4 5 6

總結(jié)

以上是生活随笔為你收集整理的【牛客 - 303B第十五届浙江大学宁波理工学院程序设计大赛（同步赛）】Fibonacci and Counting（Fib数性质，gcd辗转相除法性质）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。