c++ - 斐波那契数平方和的最后一位

问题描述

#include <iostream>
using namespace std;

int previous_fibonacci_last_digit(unsigned long long m) {
int previous = 0, current = 1;
for (unsigned long long i = 2; i <= m; i++) {
    int tmp_previous = previous;
    previous = current;
    current = ((tmp_previous % 10) + (current % 10)) % 10;

   return current;
}

int last_digit(unsigned long long n) {
     int lastDigit = ( previous_fibonacci_last_digit(n) * ( ( previous_fibonacci_last_digit(n) + previous_fibonacci_last_digit(n - 1) ) % 10 ) ) % 10 ; // found the last digit of the sum of squares of n fib numbers

     return lastDigit;
  }

为了找到 n 个 fib 数的平方和的最后一位，我发现总和可以写为 F(n) {F(n) + F(n-1)} 并且我正在为大值实现它。当我使用 long long int 时，我的程序在 n = 260548 处崩溃，所以我将其更改为 unsigned long long int，现在我的程序在 n = 519265 处崩溃。

我尝试通过在函数中添加一个 cout 来查看循环是否一直到 500000 来调试它，previous_Fibonacci_last_digit()但我发现当 n = 519265 时循环甚至没有运行到 500000。我只是存储每个斐波那契数的最后一位所以我不'不要认为其中有任何整数溢出。

编辑 - 现在不是使用数组，而是在使用变量存储最后一位数字之后，程序可以正常工作，但是将它用于 n = 1234567890，这需要很多时间。

标签： c++sumfibonacci

    #include <bits/stdc++.h>

using namespace std;

int fib(long long num ){
    int pre=0,cur=1;
    num = num %60;
    if(num==0){
        return 0;}
    else if (num == 1){
        return 1;
    }
    else{
    for (int i =2; i<=num; i++){
        int temp = (pre+cur)%60;
        pre = cur;
        cur = temp;
        // cout<<pre<<"\n"<<cur<<"\n";
    }
    }
    
    return(cur); 
}

int main() {
    long long n = 0;
    cin >> n;
    int a = fib(n);
    int b = fib(n+1);
    
    cout<<(a*b)%10;
    
    
}

最多可以计算任何斐波那契数的平方和，而无需显式地将平方相加。

如你看到的

F1^2+..Fn^2 = Fn*Fn+1

现在要计算 Fn 和 Fn+1 的最后一位，我们可以应用皮萨诺周期法

最后一位可以通过 %10 计算出来，mod 10 的 Pisano 周期是 60。所以，直接在代码中使用 %60...

c++ - 斐波那契数平方和的最后一位

问题描述

解决方案

推荐阅读