首页 > 代码库 > [NOIP1997] P2626 斐波那契数列（升级版）
[NOIP1997] P2626 斐波那契数列（升级版）
题目背景
大家都知道，斐波那契数列是满足如下性质的一个数列： • 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年的陈酿题……要是以当时的设备水平，真不知道该怎么做了。
然而现在是小水题了。
先打个素数表，再模拟搞出来斐波那契数，之后质因数分解即可。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 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<m;i++){22 if(!vis[i]){23 pri[++cnt]=i;24 }25 for(int j=1;j<=cnt && pri[j]*i<mxn;j++){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 }
[NOIP1997] P2626 斐波那契数列（升级版）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。