大意略。
思路:
素数定理:GCD(F_n, F_m) = F_GCD(n, m),则Fibonacci_Prime[k] = Fibonacci[Prime[k]],( k >= 3)
http://en.wikipedia.org/wiki/Fibonacci_prime
一开始用大数算出了14位左右的FIbonacci素数在9位,15就是10位,然后用Fibonacci通项公式去算>=15的素数时,精度丢失比较严重,精确的范围在20000左右,我怀疑它是估计把数据出到22000,泪奔。
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> #include <cmath> using namespace std; typedef unsigned long long ULL; const int MAXN = 250100; const int maxn = 1100; ULL prime[MAXN]; bool vis[MAXN] = {0}; int tot; int n; struct bign { int len, s[maxn]; bign () { memset(s, 0, sizeof(s)); len = 1; } bign (int num) { *this = num; } bign (const char *num) { *this = num; } bign operator = (const int num) { char s[maxn]; sprintf(s, "%d", num); *this = s; return *this; } bign operator = (const char *num) { len = strlen(num); for(int i = 0; i < len; i++) s[i] = num[len-i-1] - '0'; return *this; } bign operator + (const bign &b) const //+ { bign c; c.len = 0; for(int i = 0, g = 0; g || i < max(len, b.len); i++) { int x = g; if(i < len) x += s[i]; if(i < b.len) x += b.s[i]; c.s[c.len++] = x % 10; g = x / 10; } return c; } void print() { for(int i = len-1; i >= 0; i--) printf("%d", s[i]); printf("\n"); } }; bign f[2200]; void init() { tot = 1; for(int i = 2; i < MAXN; i++) if(!vis[i]) { prime[tot++] = i; for(ULL j = i*i; j < MAXN; j += i) vis[j] = 1; } prime[1] = 3, prime[2] = 4; f[1] = 1, f[2] = 1; for(int i = 3; i <= prime[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); double p = a - (ULL)a; ULL t = ULL(pow(10.0, p) * pow(10.0, 8.0)); return t; } void solve() { if(n <= 14) { f[prime[n]].print(); } else { ULL ans = cal(prime[n]); printf("%llu\n", ans); } } int main() { init(); while(~scanf("%d", &n)) { solve(); } return 0; }