uva 10236 斐波拉契素数问题

这个对你会有帮助：http://en.
GCD(F_n, F_m) = F_GCD(n, m)
Fibonacci_Prime[k] = Fibonacci[Prime[k]], k >= 3
再根据Fibonacci的通项公式(就是用黄金分割率表示的那个，这儿贴公式不方便，不写了～)，就可以求出前9位数字了。

为什么没有翻译... ...还有，这个贴为什么被设为高亮？？？？

推敲过了，我的想法是错的。
那个“素数位的斐波那契数是素数”是错的

要结贴了！
通过：GCD(F_n, F_m) = F_GCD(n, m)
可以证明：素数位的斐波那契数是斐波那契素数！
稍后间上传代码0...0

置顶有什么问题   要理解  难得使用下版主身份 ~~~~~

OK!!!!!!!!
#include<cstdio>
#include<cstring>
#include<cmath>
const int num=249439;
int prime[22001];   //素数
bool boprime[num+1];
double f[num+1];       //斐波那契数列
double goldnum;     //goldnum黄金分割比
int n;   

void find()
{
     //fill
     memset(boprime,0,sizeof(boprime));
     //find prime
     prime[0]=2; prime[1]=3; prime[2]=4;
     int i=2,j;
     while (i<=num)
     {
           if (!boprime[i])
           {
              j=2*i;
              while (j<=num)
              {
                    boprime[j]=true;
                    j+=i;
              }
              if (i!=2 && i!=3)
              prime[++prime[0]]=i;
           }
           i++;
     }
}

void doit()
{
     goldnum=(sqrt(5)-1)/2;
     f[1]=f[2]=1;
     for (int i=3;i<=83;i++) f[i]=f[i-1]+f[i-2];
     for (int i=40;i<=83;i++) while (f[i]>=1000000000) f[i]/=10;
     for (int i=84;i<=num;i++)
     {
         f[i]=f[i-1]/goldnum;
         while (f[i]>=1000000000) f[i]/=10;
     }
}

void init()
{
     while (scanf("%d",&n)==1)
       printf("%.lf\n",floor(f[prime[n]]));
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    find();
    doit();
    init();
    return 0;
}

看看我的程序如何解决精度问题！！！
本以为可以AC，谁知是WA

好惨啊！弄了我这么久...
还好最后AC了
#include<cstdio>
int n;
int tot=0;
int ans[25000];

int main()
{
    long long t0,t1=1,t2=1;
    for (int i=3;tot<22000;i++)
    {
        t0=t1+t2;
        t2=t1;
        t1=t0;
        if (t0>=1e18)
        {
           t0/=10;
           t1/=10;
           t2/=10;
        }
        bool p=true;
        for (int j=2;j*j<=i;j++)
            if (i%j==0)
            {
               p=false;
               break;
            }
        if (p || i==4)
        {
           long long p=t0;
           while (p>=1e9) p/=10;
           ans[++tot]=p;
        }
    }
    while (scanf("%d",&n)==1) printf("%d\n",ans[n]);
    return 0;
}

我TLE了好久

[ 本帖最后由 schnee 于 2011-9-20 20:05 编辑 ]