P2626 斐波那契数列(升级版)(合数的质数分解, 大数为素数的
发布时间:2020-12-14 03:47:10 所属栏目:大数据 来源:网络整理
导读:题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: f(1)=1f(1) = 1 f ( 1 ) = 1 f(2)=1f(2) = 1 f ( 2 ) = 1 f(n)=f(n?1)+f(n?2)f(n) = f(n-1) + f(n-2) f ( n ) = f ( n ? 1 ) + f ( n ? 2 ) ( n≥2n ≥ 2 n ≥ 2 且 nn n 为整数)。 题目描述
题目背景大家都知道,斐波那契数列是满足如下性质的一个数列:
题目描述请你求出第nnn个斐波那契数列的数mod(或%)2312^{31}231之后的值。并把它分解质因数。 输入输出格式输入格式: ? n ? 输出格式: ? 把第nnn个斐波那契数列的数分解质因数。 ? 输入输出样例
输入样例#1:
复制
5
输出样例#1:
复制
5=5
输入样例#2:
复制
6
输出样例#2:
复制
8=2*2*2 说明n≤48n le 48n≤48 ? 思路:本来用了矩阵快速幂(没看n的范围以为很大)但是死活不过因为n=48和n=47时,斐波拉契数列的值不对,但是n>48的值 都是对的,所以我就改用了比较直接的方法。 但是本题主要是用了合数分解为质数乘积的模板和利用大数是素数的概率很小的技巧。 #include<iostream> #define ll long long #define mod 2147483648 using namespace std; int main() { ll num[50]; num[1] = num[2] = 1; for (int i = 3; i < 50; ++i) num[i] = (num[i - 1] + num[i - 2]) % mod; int n; cin >> n; ll kk = num[n]; ll num1[200],cnt = 0; for (ll i = 2; kk != 1; ++i) { while (kk%i == 0) { num1[cnt++] = i; kk /= i; } if (i > 1000)break; } if (kk != 1)num1[cnt++] = kk; cout << num[n] << "="; for (int i = 0; i < cnt; ++i) { cout << num1[i] << "*n"[i == cnt - 1]; } } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |