题目背景
大家都知道，斐波那契数列是满足如下性质的一个数列： • 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
97年的陈酿题……要是以当时的设备水平，真不知道该怎么做了。
然而现在是小水题了。
先打个素数表，再模拟搞出来斐波那契数，之后质因数分解即可。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const long long mod=<<;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int pri[mxn],cnt;
bool vis[mxn];
void Pri(){
int m=sqrt(mxn);
for(int i=;i<m;i++){
if(!vis[i]){
pri[++cnt]=i;
}
for(int j=;j<=cnt && pri[j]*i<mxn;j++){
vis[pri[j]*i]=;
if(i%pri[j]==)break;
}
}
return;
}
void dvi(long long x){
int i,j;
bool flag=;
for(i=;i<=cnt;i++){
while(x%pri[i]==){
if(!flag)printf("%d",pri[i]);
else printf("*%d",pri[i]);
flag=;
x/=pri[i];
}
}
if(x>){
if(!flag)printf("%lld",x);
else printf("*%lld",x);
}
printf("\n");
return;
}
int n;
long long f[];
int main(){
n=read();
Pri();
f[]=;f[]=;
for(int i=;i<=n;i++){
f[i]=(f[i-]+f[i-])%mod;
}
printf("%lld=",f[n]);
dvi(f[n]);
return ;
}