UVA_10236

    这个题目AC得太辛苦了，也再一次加深了对浮点数误差的理解，库函数能不调还是最好别调……其实后来感觉就像UVA论坛上一个人说的，AC这个题有两个准则，第一个是要用long double，第二个是不要相信fmod、sqrt、pow等这些库函数，它们都会带来精度上的问题。

    下面回到题目，这个题目涉及的知识还是满多的，又让我学到了不少。首先，我们要知道fibonacci素数的特征，fibonacci数列的第3、4项的2、3为fibonacci素数，第5项及其之后的素数项均为fibonacci素数，因此我们就要知道第22000个素数大概在什么范围。百度了之后发现10^6之内可以产生7万多个素数，因此我们可以先把10^6内的素数筛出来存到数组里，以便后面使用。

    下面我们就要知道从什么时候开始fibonacci数会超过9位，我测了一下第44个fibonacci数是最后一个9位及9位以内的fibonacci数，对应的就是第14个fibonacci素数，因此我们先可以预处理出15以内的结果，剩下的再用函数去算。

    在算的时候，我们首先要找到第n个fibonacci素数的项数x，然后再求F(x)的前9位即可，在求的时候为了确保有9位精度，我们选择用long double形式的快速幂去计算，并且每次计算完之后，要把结果卡在某个范围以下，这样是为了避免后续的运算会超过long double的表示范围。

#include
     
       #include
      
        #include
       
         long long int fib[60]; int N, prime[1000010], p[100010]; long double a[60][4], b[4]; void prepare() {
   int i, j, k, n;     fib[0] = 0, fib[1] = 1; for(i = 2; i < 50; i ++)         fib[i] = fib[i - 1] + fib[i - 2];     k = (int)sqrt((double)1000001);     memset(prime, -1, sizeof(prime));     n = 0; for(i = 2; i <= k; i ++) if(prime[i])         {
               p[n ++] = i; for(j = i * i; j < 1000001; j += i)                 prime[j] = 0;         } for(; i < 1000001; i ++) if(prime[i])             p[n ++] = i;     a[0][0] = a[0][1] = a[0][2] = 1;     a[0][3] = 0; } void pow_mod(int n, int e) {
   if(n == 1)     {
           a[e][0] = a[e][1] = a[e][2] = 1;         a[e][3] = 0; return ;     }     pow_mod(n / 2, e + 1);     a[e][0] = a[e + 1][0] * a[e + 1][0] + a[e + 1][1] * a[e + 1][2];     a[e][1] = a[e + 1][0] * a[e + 1][1] + a[e + 1][1] * a[e + 1][3];     a[e][2] = a[e + 1][2] * a[e + 1][0] + a[e + 1][3] * a[e + 1][2];     a[e][3] = a[e + 1][2] * a[e + 1][1] + a[e + 1][3] * a[e + 1][3]; if(n % 2)     {
           b[0] = a[e][0] * a[0][0] + a[e][1] * a[0][2];         b[1] = a[e][0] * a[0][1] + a[e][1] * a[0][3];         b[2] = a[e][2] * a[0][0] + a[e][3] * a[0][2];         b[3] = a[e][2] * a[0][1] + a[e][3] * a[0][3];         a[e][0] = b[0], a[e][1] = b[1], a[e][2] = b[2], a[e][3] = b[3];     } while(a[e][0] > 10000)         a[e][0] /= 10, a[e][1] /= 10, a[e][2] /= 10, a[e][3] /= 10; } void solve() {
   int i, j, n; long long int t; long double x;     n = p[N - 1];     pow_mod(n - 1, 1);     x = a[1][0]; while(x < 100000000)         x *= 10;     t = (long long int)x;     printf("%lld\n", t); } int main() {
       prepare(); while(scanf("%d", &N) == 1)     {
   if(N <= 2)             printf("%s\n", N == 1 ? "2" : "3"); else if(N <= 14)             printf("%lld\n", fib[p[N - 1]]); else             solve();     } return 0; }