大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)。
1 /*by SilverN*/
2 #include
3 #include
4 #include
5 #include
6 #include
7 #include
8 using namespace std;
9 const long long mod=1<<31;
10 const int mxn=3000000;
11 int read(){
12 int x=0,f=1;char ch=getchar();
13 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
14 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
15 return x*f;
16 }
17 int pri[mxn],cnt;
18 bool vis[mxn];
19 void Pri(){
20 int m=sqrt(mxn);
21 for(int i=2;i){
22 if(!vis[i]){
23 pri[++cnt]=i;
24 }
25 for(int j=1;j<=cnt && pri[j]*i){
26 vis[pri[j]*i]=1;
27 if(i%pri[j]==0)break;
28 }
29 }
30 return;
31 }
32 void dvi(long long x){
33 int i,j;
34 bool flag=0;
35 for(i=1;i<=cnt;i++){
36 while(x%pri[i]==0){
37 if(!flag)printf("%d",pri[i]);
38 else printf("*%d",pri[i]);
39 flag=1;
40 x/=pri[i];
41 }
42 }
43 if(x>1){
44 if(!flag)printf("%lld",x);
45 else printf("*%lld",x);
46 }
47 printf("\n");
48 return;
49 }
50 int n;
51 long long f[49];
52 int main(){
53 n=read();
54 Pri();
55 f[1]=1;f[2]=1;
56 for(int i=3;i<=n;i++){
57 f[i]=(f[i-1]+f[i-2])%mod;
58 }
59 printf("%lld=",f[n]);
60 dvi(f[n]);
61 return 0;
62 }