首页 > 代码库 > 斐波那契数列（升级版）
斐波那契数列（升级版）
题目背景
大家都知道，斐波那契数列是满足如下性质的一个数列： • 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
代码
#include<cmath>#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;int read(){ int x=0,f=1; char ch=getchar(); while(ch<‘0‘||ch>‘9‘) { if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘&&ch<=‘9‘) { x=x*10+ch-‘0‘; ch=getchar(); } return f*x;}//读入优化 int main(){ int p=pow(2,31); int n=read(); double x=sqrt(5.0); long long s=(pow(((1+x)/2),n)/x-pow(((1-x)/2),n)/x);//斐波那契数列通项公式 s=s%p;//取模运算 printf("%lld=",s); long long sum=0; int m=2; while(s!=1) { if(s%m) m++; else { sum++; if(sum==1) printf("%d",m); else printf("*%d",m); s/=m; } }//分解质因数 return 0;}
斐波那契数列（升级版）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。