没有思路,只能先写写
/*
1 1 2 3 5 8 13
(x,y)
(y,x%y)
8k+5 5k+3
5k+3 3k+2
3k+2 2k+1
2k+1 k+1
k+1 k
k 1
1 0
由于k=1时以上的各数皆是互质,那么就显然是斐波那契数列了
*/
代码如下:
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll f[105]; int main(){ ll n; cin >> n; f[1] = 1ll; f[2] = 1ll; for(int i=3;i<=100;i++) f[i] = f[i-1] + f[i-2]; int ans; for(int i=1;i<=100;i++){ if(f[i] > n){ ans = i - 1; break; } } cout << ans << endl; return 0; }