大意不再赘述。
思路:由于我怕精度丢失,所以在1~30内的Fibonacci,我都直接算出来,大于30的用通项公式算。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <cmath> using namespace std; typedef unsigned long long ULL; ULL f[31]; int n; void init() { f[1] = 1, f[2] = 1; for(int i = 3; i <= 31; i++) f[i] = f[i-1]+f[i-2]; } ULL cal(int n) { double f = (1.0+sqrt(5.0))/2.0; double a = -0.5*log10(5.0)+((double)n)*log10(f); ULL ans = (ULL)a + 1; return ans; } void solve() { if(n <= 30) { double ans = log10(f[n])+1.0; printf("%llu %llu\n", (ULL)ans, f[n]); } else printf("%llu\n", cal(n)); } int main() { init(); int T; scanf("%d", &T); while(T--) { scanf("%d", &n); solve(); } return 0; }