题目背景

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

 这个公式求不出第2项斐波那契数列的值  = =

 质因数分解

#include 
     
      #include 
      
       typedef long long LL;int n;int main(){    scanf("%lld",&n);    double x=sqrt(5.0);    LL ans=1/x*((pow((1+x)/2,n))-pow((1-x)/2,n));    ans=ans%2147483648;    bool flag=false;    printf("%lld=",ans);    LL k=2;    while(ans!=1)    {        while(ans%k==0)        {            ans/=k;            if(!flag)            {                printf("%d",k);                flag=true;            }            else printf("*%d",k);        }        k++;    }    return 0;}