Fibnaci

谈谈如何设计算法快速求出斐波那契第$n(n < 10^{18})$项？由于结果很大，因此输出对99999989取模的结果。

提示：1、99999989是质数；2、浮点数在经历多次运算后可能会出现精度不够的情况而导致答案错误；3、中的pow函数很慢，因此您可能需要重新设计pow函数。

参考公式：斐波那契的通项公式为：

$\frac 1 {\sqrt{5}}[(\frac {1+\sqrt{5}} 2)^n-(\frac {1-\sqrt{5}} 2)^n]$

参考答案：

#include <stdio.h>

typedef long long ll;
int MOD = 99999989; //模数，这里保证是一个奇质数
int inv5 = 50122571; // 根号5的对MOD取模的结果，暴搜得到
//这是负根号5：49877418
//也可以用二次剩余定理求，但这里没必要

// 朴素快速幂，时间上已经足够所以没有用欧拉函数优化
int qpow(int base, ll p, int mod) {
    if (p <= 0) return 1;
    int res = qpow(base, p >> 1, mod);
    res = res * 1ll * res % mod;
    if (p & 1)  res = res * 1ll * base % mod;
    return res;
}

// 逆元，费马小定理
int inv(int x, int mod) {
    return qpow(x, mod - 2, mod);
}

// 模意义下取绝对值
int abs(int x, int mod) {
    return (x % mod + mod) % mod;
}

//用通项公式求斐波那契第n项，时间 O(log MOD)
int fib(int n, int mod) {
    int a = abs(1 + inv5, mod) * 1ll * inv(2, mod) % mod;
    int b = abs(1 - inv5, mod) * 1ll * inv(2, mod) % mod;
    return inv(inv5, mod) * 1ll * abs(qpow(a, n, mod) - qpow(b, n, mod), mod) % mod;
}

int main() {
    int n, mod = MOD;
    scanf("%d", &n);
    printf("%d\n", fib(n, mod));
    return 0;
}