首页 > 代码库 > hdu 3117 Fibonacci Numbers
hdu 3117 Fibonacci Numbers
这道题其实也是水题来的，求Fibonacci数的前4位和后4位，在n==40这里分界开。后4位不难求，因为n达到了10^18的规模，所以只能用矩阵快速幂来求了，但在输出后4位的时候一定要注意前导0的处理（我就是在这里wa了一发，也是看了看别人的代码才发现的）。
前4位的话稍微有点难处理，我一开始就在想该怎么处理 log10(f(n)) 呢？把f[n]= f[n-1]+f[n-2]? 不行，log对+运算没法展开，我找了好久也没能找到什么能让f[n]展开成相乘或者幂的形式，上网搜了下题解，才发现别人竟然是用通项公式来处理的（我当时也想过，但因为含有"-"运算所以就直接忽略了，可是没想到其实可以稍微变通下就可以把"-"号去掉的）： f(n)= 1/sqrt(5) (( (1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n );
具体实现的时候Log10 F[n]约等于 ((1+sqrt(5))/2)^n/sqrt(5)，这里我们把 ((1-sqrt(5))/2)^n这一项忽略了，因为当N>=40时，这个数已经小的可以忽略。于是log10 F[n]就可以化简成 n*log10( (1+sqrt(5))/2 ) -log10 sqrt(5)，不多说，附上代码：
1 #include<cstdio> 2 #include<cmath> 3 #include<cstring> 4 #define For(i,s,t) for(int i=s; i<=t; ++i) 5 typedef long long LL; 6 const LL mod= 10000; 7 8 struct matrix{ 9 LL a,b,c,d;10 matrix(LL a=0, LL b=0, LL c=0, LL d=0):a(a),b(b),c(c),d(d) {}11 matrix operator *(const matrix &m2) const {12 return matrix((a*m2.a%mod+b*m2.c%mod)%mod, (a*m2.b%mod+b*m2.d%mod)%mod, (c*m2.a%mod+d*m2.c%mod)%mod, (c*m2.b%mod+d*m2.d%mod)%mod);13 }14 } A(1,1,1,0),E(1,0,0,1);15 16 matrix quick_mod(matrix m, LL b){17 matrix res(E);18 while(b){19 if(b&1) res= res*m;20 m= m*m;21 b>>=1;22 }23 return res;24 }25 26 void solve(LL n){27 LL last= quick_mod(A,n-1).a;28 // int last= int(quick_mod(A,n-1).a);29 double m= n*log10((1+sqrt(5.0))/2)-log10(sqrt(5.0));30 m -= LL(m);31 LL first= LL(pow(10.0,m)*1000);32 //一定要有04d！后4位的前导0也要输出！ 33 printf("%I64d...%04I64d\n",first,last);34 }35 36 LL f[40]= {0,1,1};37 void init(int n=39){38 For(i,3,n) f[i]= f[i-1]+f[i-2];39 }40 41 int main(){42 init();43 LL n;44 while(~scanf("%I64d",&n)){45 if(n<40) printf("%I64d\n",f[n]);46 else solve(n);47 }48 return 0;49 }
很神奇的是，用 I64d来输出前4位竟然是0ms（直接%04d的话却是15ms），好像第一次排上了hdu榜上的第一页，哈哈~~附上一张图：
hdu 3117 Fibonacci Numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。