P2626 斐波那契数列（升级版）

admin

题目背景
大家都知道，斐波那契数列是满足如下性质的一个数列：
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

universehyf

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. }

复制代码