所以我必须找到一个斐波那契序列不同的起始号，但有一个锻炼，我想不通为什么我的代码工作的大部分时间，而不是在一些情况下。
我的代码是基于式（链接： https://www.geeksforgeeks.org/program-for-nth-fibonacci-number/ ）
If n is even then k = n/2:
F(n) = [2*F(k-1) + F(k)]*F(k)
If n is odd then k = (n + 1)/2
F(n) = F(k)*F(k) + F(k-1)*F(k-1)
-
#include <map>
#include <iostream>
#include <cmath>
using namespace std;
#define long long long
map<long, long> F;
long f(long n, long M) {
if (F.count(n)) return F[n];
long k = n / 2;
if (n % 2 == 0) { // n=2*k
return F[n] = (f(k, M)*f(k, M) + f(k - 1, M)*f(k - 1, M)) % M;
}
else { // n=2*k+1
return F[n] = (f(k, M)*f(k + 1, M) + f(k - 1, M)*f(k, M)) % M;
}
}
int main() {
long a, b, M, n;
cin >> a >> b >> n >> M;
M = pow(10, M); //modulo
F[0] = b;
F[1] = a + b;
//base cases
for (int i = 2; i < 100; i++) F[i] = (F[i - 1] + F[i - 2]) % M;
if (n != 0) cout << f(n - 1, M) << endl;
else cout << a<<endl;
F.clear();
}
一个 - 是该序列的第一个数字。 b - 第二个。 N - 这是我想要找的序列号。 米 - 模。
我不明白为什么它有样病例工程
98 25 1000000000 1 //answer is 3
但它不工作
34 88 224242 2 //my answer is 12, correct is 92
代码工作正常定期斐波那契数开始（0和1）
我会是你的帮助非常感激。
谢谢。
