首页 > 其他 > 详细

斐波那契数列

时间：2014-04-19 10:18:27      阅读：427      评论：0      收藏：0      [点我收藏+]

  1. F[0]=0;

    F[1]=1;

    F[n]=F[n-1]+F[n-2], for n>1

    给出n (0<=n<=10000) 和 m (0<m<10000);求斐波那契数列第n项mod m的值(因为太大了);

  3. #include<stdio.h>
  4. #include<string.h>
  5. // 矩阵快速幂
  6. void xx(longlong a[][3],longlong b[][3],longlong m){
  7. longlong tmp[3][3];
  8. tmp[1][1]= tmp[1][2]= tmp[2][1]= tmp[2][2]=0;
  9. for(int i =1; i <=2; i++){
  10. for(int j =1; j <=2; j++){
  11. for(int k =1; k <=2; k++){
  12. tmp[i][j]+=(a[i][k]%m*b[k][j]%m)%m;
  13. }
  14. }
  15. }
  16. for(int i =1; i <=2; i++)
  17. for(int j =1; j <=2; j++) a[i][j]= tmp[i][j]%m;
  18. }
  19. int main(){
  20. // ans初值是单位矩阵
  21. longlong T, ans[3][3], r[3][3], n, m;
  22. r[1][2]= r[2][1]= r[2][2]= ans[1][1]= ans[2][2]=1;
  23. r[1][1]= ans[1][2]= ans[2][1]=0;
  24. scanf("%lld%lld",&n,&m);
  25. if(!n){printf("%lld\n",0% m);return0;}
  26. if(n ==1){printf("%lld\n",1% m);return0;}
  27. n--;
  28. while(n){
  29. if(n &1) xx(ans, r, m);
  30. n >>=1;
  31. xx(r, r, m);
  32. }
  33. printf("%lld\n", ans[2][2]% m);
  34. return0;
  35. }

斐波那契数列,布布扣,bubuko.com

斐波那契数列

原文：http://www.cnblogs.com/sysu-zhengwsh/p/3674186.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！