IPCP 2005 Northern Preliminary for Northeast North-America &&Fibonacci Numbers
nを数えて、Fibonacci数のn番目の項の前の4項と後の4項を求めさせて、8項のないのは前の4項だけを出力します.
構想:後の4項は求めやすくて、2つの方法、1種はマトリックスを構築して、1種はその周期を求めます.の最初の4つはFibonacci式を使っています
コード:
構想:後の4項は求めやすくて、2つの方法、1種はマトリックスを構築して、1種はその周期を求めます.の最初の4つはFibonacci式を使っています
コード:
#include<iostream>
#include<cstdio>
#include<string.h>
#include<cmath>
#define I (1.0+sqrt(5.0))/2
#define M 10000
using namespace std;
typedef long long L;
typedef struct str
{ L s[2][2];
}Node;
Node a,b,c;
inline void init()
{ a.s[0][0]=0;a.s[0][1]=1;
a.s[1][0]=1;a.s[1][1]=1;
b.s[0][0]=1;b.s[0][1]=0;
b.s[1][0]=0;b.s[1][1]=1;
c.s[0][0]=1;c.s[0][1]=1;
c.s[1][0]=0;c.s[1][1]=0;
}
Node ceil(Node p,Node q)
{ Node aa;
memset(aa.s,0,sizeof(aa.s));
for(int i=0;i<2;++i)
for(int j=0;j<2;++j)
for(int t=0;t<2;++t)
aa.s[i][j]=(aa.s[i][j]+p.s[i][t]*q.s[t][j])%M;
return aa;
}
Node doit(int k)
{
Node p=b,q=a;
while(k)
{ if(1&k) p=ceil(p,q);
q=ceil(q,q);
k=k>>1;
}
p=ceil(c,p);//
return p;
}
int main()
{
int f[40]={0,1};
for(int i=2;i<40;++i)
f[i]=f[i-1]+f[i-2];
init();
int n;
while(~scanf("%d",&n))
{
if(n<40)
{ printf("%d
",f[n]);
continue;
}
int k=n-2;
Node bb=doit(k);
double ans=-0.5*(log10(5.0))+n*log10(I);
ans-=(int)ans;
ans=pow(10.0,ans);
while(ans<1000)
ans*=10.0;
printf("%d...",(int)ans);
printf("%04d
",bb.s[0][1]);// 0
int mm=5;
}return 0;
}