P2626 斐波那契数列(升级版)(合数的质数分解, 大数为素数的概率十分小的利用)

时间:2022-09-15 20:04:25

题目背景

大家都知道,斐波那契数列是满足如下性质的一个数列:

  • f(1)=1f(1) = 1 f(1)=1
  • f(2)=1f(2) = 1f(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 ≥ 2n≥2 且 nnn 为整数)。

题目描述

请你求出第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[];
num[] = num[] = ;
for (int i = ; i < ; ++i)
num[i] = (num[i - ] + num[i - ]) % mod;
int n;
cin >> n;
ll kk = num[n];
ll num1[], cnt = ;
for (ll i = ; kk != ; ++i)
{
while (kk%i == )
{
num1[cnt++] = i;
kk /= i;
}
if (i > )break;
}
if (kk != )num1[cnt++] = kk;
cout << num[n] << "=";
for (int i = ; i < cnt; ++i)
{
cout << num1[i] << "*\n"[i == cnt - ];
}
}

P2626 斐波那契数列(升级版)(合数的质数分解, 大数为素数的概率十分小的利用)的更多相关文章

  1. 洛谷——P2626 斐波那契数列(升级版)

    P2626 斐波那契数列(升级版) 题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ ...

  2. &lbrack;NOIP1997&rsqb; P2626 斐波那契数列(升级版)

    题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数). 题目描述 ...

  3. 洛谷——P2626 斐波那契数列(升级版)矩阵

    题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数). 题目描述 ...

  4. 洛谷 P2626 斐波那契数列(升级版)

    题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数). 题目描述 ...

  5. &lbrack;洛谷P2626&rsqb;斐波那契数列(升级版)

    题目大意:请你求出第$n$个斐波那契数列的数$mod 2^{31}$之后的值.并把它分解质因数. 题解:乱搞 卡点:1.忘记取模 C++ Code: #include<cstdio> #i ...

  6. P2626 斐波那契数列(升级版)

    题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数). 题目描述 ...

  7. P2626 斐波那契数列(升级版) 洛谷(2626)

    https://www.luogu.org/problem/show?pid=2626 题目背景 大家都知道,斐波那契数列是满足如下性质的一个数列: • f(1) = 1 • f(2) = 1 • f ...

  8. 斐波那契数列(递归)&amp&semi;求100以内的素数

    Java 5 添加了 java.util.Scanner 类,这是一个用于扫描输入文本的新的实用程序.它是以 前的 StringTokenizer 和 Matcher 类之间的某种结合.由于任何数据都 ...

  9. AC日记——斐波那契数列(升级版) 洛谷 P2626

    斐波那契数列(升级版) 思路: 水题: 代码: #include <cmath> #include <cstdio> #include <cstring> #inc ...

随机推荐

  1. 自制Unity小游戏TankHero-2D&lpar;5&rpar;声音&plus;爆炸&plus;场景切换&plus;武器弹药

    自制Unity小游戏TankHero-2D(5)声音+爆炸+场景切换+武器弹药 我在做这样一个坦克游戏,是仿照(http://game.kid.qq.com/a/20140221/028931.htm ...

  2. phpcms v9 首页怎么调取单页内容,描述,标题等

    {pc:,  v9 数据表前缀  catid 这是单页的id

  3. SGU 242 Student&amp&semi;&num;39&semi;s Morning 网络流(水

    题目链接:contest=0&problem=242">点击打开链接 题意: 给定n个人,m个终点 以下n行表示每一个人能够去m个点. 每一个人仅仅能去一个点. 输出随意一个方 ...

  4. JAR包数字签名与验证

    经签名的Jar包内包含了以下内容: 原Jar包内的class文件和资源文件 签名文件 META-INF/*.SF:这是一个文本文件,包含原Jar包内的class文件和资源文件的Hash 签名block ...

  5. ajax之全局函数

    1.全局函数:$.each(array,function(){1,value}),通过$/jQuery直接调用 对象函数:$("#name").val(); jQuery UI:$ ...

  6. &lbrack;原&rsqb;JSBSim 自动驾驶(浅出)

    jsbsim的脚本文件分为几大类: 1.系统脚本: systems  包含通用飞机各部分功能模块组件以及自动飞行控件:Autopilot.xml  和 自动飞行的算法控件:GNCUtilities.x ...

  7. StringEscapeUtils对字符串进行各种转义与反转义

    项目过程中导出的word无法打开,发现是由于里面有&字符造成,需要进行HTML字符的转义: StringEscapeUtils.escapeHtml4(“需要转义的字符”); 已解决. 参考: ...

  8. redis 集群搭建&colon; redis-cluster

    前言 redis数据存储在内存中, 就会受到内存的限制, 大家都知道, 一台电脑, 硬盘可以有1T, 但是内存, 没有听说有1T的内存吧. 那如果数据非常多, 超过一台电脑的内存空间, 怎么办呢? 正 ...

  9. mongodb&period;mongoose维护内嵌数组元素

    运行环境: - Nodejs - MongoDB 文档实例名: ProjectJob 文档格式如下: { "_id" : ObjectId("5bc69eb0b298b3 ...

  10. Vue&period;js中用webpack合并打包多个组件并实现按需加载

    对于现在前端插件的频繁更新,所以多多少少要对组件化有点了解,下面这篇文章主要给大家介绍了在Vue.js中用webpack合并打包多个组件并实现按需加载的相关资料,需要的朋友可以参考下.   前言 随着 ...