斐波那契数列部分和的最后一位

Question

我试图找到从起点到终点的斐波那契数列总和的最后一位。当我们使用 %10 找到最后一位数字时，Fibonnaci 将每 60 次重复它的最后一位数字序列 - 使用 Pisano 系列

我的解决方案尝试：

我们找到前60位的最后一位，存入数组，然后不断循环求和，从n%60到m位。然后我们最终对结果进行模 10。

#include <iostream>
#include <vector>
using std::vector;

int fibonacci_fast(long long n,long long m) {
    // write your code here
    long long a[60];
    a[0]=0;
    a[1]=1;
    long long sum=0;
    for(long long i=2;i<60;i++)
    {
        a[i] = a[i-1]+a[i-2];
        a[i] = a[i] % 10;
    }
    int j=0;
    int p=1;
    int c=0;
    for(int i=n%60;;i++)
    {
        if(i==60)
        {
            i=i%60;
        }
        sum=sum+a[i];
        c=c+1;
        if(c==m)
        {
            break;
        }
    }
    return sum%10;
}

int main() {
    long long from, to;
    std::cin >> from >> to;
    std::cout << fibonacci_fast(from, to) << '\n';
}

我当前代码遇到的主要问题是对于较低的值，它工作正常，但如果我输入较高的值，例如 0 到 239，它仅在条件更改为 if(c+1)==m 然后导致较小值的解决方案出错。

虽然 c 计数器工作正常并上升到 239，但我仍然无法找出代码的问题。

Answer 1

我认为您需要将变量 c 设置为等于 n 的值而不是 0（零）
int c = n;

另外，请弄清楚是否要包含索引m的概念。
例如，如果用户输入：
n -> 10 m -> 20
然后您上面提供的代码将仅从索引 10 到索引 19 添加斐波那契数的最后一位值。所以请解开我的这个疑惑，我再补充。

Answer 2

#include <vector>
using std::vector;

int fibonacci_fast(long long n,long long m) {
    // write your code here
    long long a[60];
    a[0]=0;
    a[1]=1;
    long long sum=0;
    sum = a[0] + a[1];
    for(long long i=2;i<60;i++)
    {
        a[i] = a[i-1]+a[i-2];
        a[i] = a[i] % 10;
        sum = (sum + a[i]) % 10;
    }
    int x = (m - n + 1)/60;
    sum = (sum * x) % 10;
    int i = n + 60 * x;
    while(i <= m)
    {
        sum = (sum + a[i%60]) % 10;
        i++;
    }
    return sum;
}

int main() {
    long long from, to;
    std::cin >> from >> to;
    std::cout << fibonacci_fast(from, to) << '\n';
}

斐波那契数列部分和的最后一位

Last digit of partial sum of Fibonacci series

c++

math

fibonacci