华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1066|回复: 1
打印 上一主题 下一主题

P2626 斐波那契数列(升级版)

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-7-14 10:26:16 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
题目背景
大家都知道,斐波那契数列是满足如下性质的一个数列:
f(1) = 1
f(2) = 1
f(n) = f(n-1) + f(n-2)) ( n>2 且 n 为整数)。
题目描述
请你求出第 nn 个斐波那契数列的数mod(或%) 2^31之后的值。并把它分解质因数。

输入输出格式
输入格式:
n

输出格式:
把第 n 个斐波那契数列的数分解质因数。

输入输出样例
输入样例#1:
5
输出样例#1:
5=5
输入样例#2:
6
输出样例#2:
8=2*2*2
说明
n≤48
回复

使用道具 举报

14

主题

106

帖子

317

积分

中级会员

Rank: 3Rank: 3

积分
317
沙发
发表于 2018-9-14 15:56:26 | 只看该作者
  1. #include<iostream>
  2. #include<cmath>
  3. using namespace std;
  4. long long n,t=2;
  5. long long s=2;
  6. long long f[50];
  7. bool b;
  8. bool ss(int xx)
  9. {
  10.     if(xx<2) return false;
  11.     for(long long i=2;i<=sqrt(xx);i++)
  12.         if(xx%i==0) return false;
  13.     return true;
  14. }
  15. void fj(int x)
  16. {
  17.     if(x==1) return;
  18.     if(ss(x)){if(b) cout<<"*";else b=true;cout<<x;return;}
  19.     long long sqr=sqrt(x);
  20.     for(long long i=t;i<=sqr;i++)
  21.         if(ss(i)&&(x%i==0))
  22.         {
  23.             if(b) cout<<"*";
  24.             else b=true;
  25.             cout<<i;
  26.             t=i;
  27.             fj(x/i);
  28.             return;
  29.         }
  30. }
  31. int main()
  32. {
  33.     cin>>n;
  34.     for(int i=2;i<=31;i++)
  35.         s=s*2;
  36.     f[1]=1;f[2]=1;
  37.     for(int i=3;i<=n;i++)
  38.         f[i]=(f[i-1]+f[i-2])%s;
  39.     cout<<f[n]<<"=";
  40.     fj(f[n]);
  41.     if(!b) cout<<f[n];
  42.     return 0;
  43. }
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 01:46 , Processed in 0.182329 second(s), 24 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表