UVa 10236 - The Fibonacci Primes

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址

找出第 n 個 fibonacci prime ，費氏數列中某數，如果和比它小的所有 $F_n$ 數字互質，就稱它為 fibonacci prime。

如果大於 9 位數，只需要輸出前 9 位。

Solution

這裡有查到一個特性，如果 n 為質數，fib[n] 也會為質數，有些特例需要處理，詳細請看 Fibonacci Prime。

fib[2] = 2;
fib[3] = 3;

這裡還有個 fib[prime[8]] = fib[19] = 4181 ，$ 4181 = 37 \times 113$ ，並沒有處理到，不過不知為何還是拿了 AC …

費氏數列增長很快，一下就變得要處理大數了，這裡可以使用 double ，因為只需要前九位精準即可，只要數字超過 1e9 就將它除以 10。

p.s. 記得輸出時要轉型，避免四捨五入的情況發生。

Code

UVa 10236UVa 10236 - The Fibonacci Primes

#include<cstdio>
#include<cmath>
#define MAX 300000
#define N 250000
#define M 22001

bool sieve[MAX];
int prime[M];
void getPrime();

double fib[N] = { 0, 1 };
void getFibPrime();
int main()
{
    getPrime();
    getFibPrime();
    int n;

    /*
    fibonacci 在 index 為質數時，fib[index] 也會是質數，也就是 fibonacci prime
    有一些特殊的狀況，這邊沒有處理到 index = 19 (prime[8])時，fib[index] 卻不為質數
    */
    fib[2] = 2;
    fib[3] = 3;
    while (scanf("%d", &n) != EOF)
        printf("%d\n", (int)fib[prime[n]]);
    
    return 0;
}
void getPrime()
{ 
    int s = sqrt(MAX);
    for (int i = 2; i < s; i++)
    {
        if (!sieve[i])
        {
            for (int j = i <<1; j < MAX; j += i)
                sieve[j] = true;
        }
    }

    //prime[] 從 1 開始，方便計算
    int count = 1;
    for (int i = 2; i < MAX; i++)
    {
        if (!sieve[i])
            prime[count++] = i;
    }
}
void getFibPrime()
{
    //count fibonacci
    bool div = false;
    for (int i = 2; i < N; i++)
    {
        if (div)
        {
            fib[i] = fib[i - 1] + fib[i - 2] / 10;
            div = false;
        }
        else
            fib[i] = fib[i - 1] + fib[i - 2];

        //超出 9 位數後，最後一位退一位
        if (fib[i] >= 1e9)
        {
            fib[i] /= 10;
            div = true;
        }
    }
}