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

题目要求

题目链接

分析

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

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

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

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

AC代码

#include 
#include 

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