大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)。
请你求出第n个斐波那契数列的数mod(或%)2^31之后的值。并把它分解质因数。
输入格式:
n
输出格式:
把第n个斐波那契数列的数分解质因数。
输入样例#1:
5
输出样例#1:
5=5
输入样例#2:
6
输出样例#2:
8=2*2*2
n<=48
1 #include<iostream>
2 using namespace std;
3 int a[1001];
4 int main()
5 {
6 int n;
7 cin>>n;
8 int ans=0;
9 a[1]=1;
10 a[2]=1;
11 for(int i=3;i<=n;i++)
12 {
13 a[i]=a[i-1]+a[i-2];
14 }
15 ans=a[n];
16 cout<<ans<<"=";
17 int j=2;
18 int flag=0;
19
20 while(ans!=1)
21 {
22 while(ans%j==0)
23 {
24 if(flag==0)
25 {
26 cout<<j;
27 flag=1;
28 }
29 else
30 {
31 cout<<"*"<<j;
32 }
33 ans=ans/j;
34 }
35
36 j++;
37 }
38
39 if(flag==0)
40 {
41 cout<<a[n];
42 }
43 /*for(int i=3;i<=n;i++)
44 {
45 int j=2;
46 int flag=0;
47 while(j*j<a[i])
48 {
49 while(a[i]>1)
50 {
51 if(a[i]%j==0)
52 {
53 cout<<j<<"*";
54 a[i]=a[i]/j;
55 }
56 else
57 break;
58 }
59 j++;
60 }
61 }
62 cout<<ans;
63 //cout<<a[n];*/
64 return 0;
65 }