題目背景 大家都知道，斐波那契數列是滿足如下性質的一個數列： • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 為整數)。 題目描述 請你求出第n個斐波那契數列的數mod（或%）2^31之後的值。並把它分解質因數。 輸入輸出格式 輸入 ...
題目背景
大家都知道，斐波那契數列是滿足如下性質的一個數列： • 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 }
