斐波那契数列升级版（洛谷P2626题题解，C++语言描述）

ゝ一世哀愁。 2022-10-22 04:26 219阅读 0赞

# 题目要求 #

[题目链接][Link 1]

![在这里插入图片描述][20210404011738426.png]

# 分析 #

首先是求斐波那契数列，这东西我就不说了，能看到这篇题解的你肯定会。  
为什么要用数组呢？为了记忆化，防止重复算。  
当然，由于本题是单查询，所以不必记忆化，但记忆化对多查询真的会好很多，空间换时间。

mod是已经计算好的，避免重复求，节省时间，注意 2 31 2^\{31\} 231不爆int。

分解质因数的话，就疯狂怼着尽可能小的因子往下整除。  
由于已经把小因子除尽，所以已经消灭了非质数再被整除的可能，所以能再被整除的肯定是质因数，这样就避免了打一个素数筛。

其他的就是输出格式咯，不谈，看代码即可。

# AC代码 #

#include <iostream>
    #include <cmath>
    
    using namespace std;
    
    const int mod = pow(2, 31);
    
    int fib[49] = {
        0, 1, 1};
    
    int main() {
        
        int n;
        cin >> n;
        for (int i = 3; i <= n; i++) {
        
            fib[i] = (fib[i-1] + fib[i-2]) % mod;
        }
        cout << fib[n] << "=";
        bool flag = false;
        for (int i = 2; i <= fib[n]; i++) {
        
            while (fib[n] % i == 0) {
        
                if (!flag) {
        
                    flag = true;
                    cout << i;
                } else {
        
                    cout << '*' << i;
                }
                fib[n] /= i;
            }
        }
        return 0;
    }

[Link 1]: https://www.luogu.com.cn/problem/P2626
[20210404011738426.png]: /images/20221022/ce27ee1bbc184811bd541f611eb159ca.png

发表评论取消回复

表情：

评论列表（有 0 条评论，219人围观）

还没有评论，来说两句吧...

相关阅读

相关（C语言）斐波那契数列

有另一种斐波那契数列：F(0)=7,F(1)=11,F(n)=F(n-1)+F(n-2) (n>=2) 用递归求第n项。输入格式: 输入一个正整数n（1<=n<=20）

水深无声/ 2023年07月16日 12:55/ 0 赞/ 39 阅读

相关 c语言斐波那契数列

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

一时失言乱红尘/ 2023年07月01日 12:00/ 0 赞/ 31 阅读

相关【洛谷P1962】斐波那契数列

Description 给定n，求斐波那契数列第n项对1e9+7取模的值 Solution 由于数据太大，朴素的递推会超时，所以我们考虑用矩阵优化。首先我们要

梦里梦外;/ 2023年06月05日 08:52/ 0 赞/ 61 阅读

相关斐波那契数列C语言详解

编译环境：vc6.0 include <stdio.h> int fibonacci(int n) { if(n == 1)

迷南。/ 2023年03月14日 10:47/ 0 赞/ 52 阅读

相关数列求和（洛谷P5745题题解，C++语言描述）

题目要求 [题目链接][Link 1] ![在这里插入图片描述][20210404021812720.png] 分析思路参考自[大佬的博客][Link 2]，

矫情吗；*/ 2022年10月22日 04:26/ 0 赞/ 254 阅读

相关斐波那契数列升级版（洛谷P2626题题解，C++语言描述）

题目要求 [题目链接][Link 1] ![在这里插入图片描述][20210404011738426.png] 分析首先是求斐波那契数列，这东西我就不说了，能

ゝ一世哀愁。/ 2022年10月22日 04:26/ 0 赞/ 220 阅读

相关 P09 斐波那契数列

斐波那契数列的第N位=(N-1)+(N-2)；开始仅知道第一位和第二位的值为0和1。求第N位的值的算法 > 0 1 2 3 5 8 13 21 34 55 … (n-2) (

小灰灰/ 2022年10月19日 12:59/ 0 赞/ 179 阅读

相关 C++——斐波那契数列

C++——斐波那契数列 1. 斐波那契数列斐波那契数列的特征是为0开始，接下来两位数为1或者直接前两位为1开始，从第三位开始，后一位是前面两位之和（也可以看做增加

女爷i/ 2022年10月04日 13:57/ 0 赞/ 216 阅读

相关斐波那契数列-C语言实现

include <stdio.h> include <stdlib.h> int main() { int n = 0

左手的ㄟ右手/ 2022年06月04日 00:26/ 0 赞/ 239 阅读

相关洛谷 P1306 斐波那契公约数

[https://www.luogu.org/problem/show?pid=1306][https_www.luogu.org_problem_show_pid_1306

迷南。/ 2021年12月18日 07:43/ 0 赞/ 257 阅读