基于Pisano周期计算大斐波那契数模值的代码问题求助

Let's break down why your code fails with larger Pisano cycles and fix it step by step:

Key Issues in Your Code #

• Incorrect Cycle Termination Check: The Pisano cycle starts with 0, 1, so we need to stop when we see this pair again at the end of the sequence. Your code checks for 1, 0 as the last two elements, which is the reverse of the correct condition. This causes the function to exit early or miss the actual cycle end for larger values of m.
• Unmodded Intermediate Values Cause Overflow: You're storing fib%m in the series, but n1 and n2 themselves keep growing without taking %m. For larger cycles, these values will overflow unsigned long long, leading to incorrect calculations of subsequent Fibonacci numbers and their moduli.

Fixed Code #

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

typedef unsigned long long ll;

vector<ll> pisano(ll m) {
    ll n1 = 0;
    ll n2 = 1;
    vector<ll> pisanoseries;
    pisanoseries.push_back(n1);
    pisanoseries.push_back(n2);
    
    while (true) {
        // Calculate next Fibonacci number modulo m to prevent overflow
        ll next_fib = (n1 + n2) % m;
        pisanoseries.push_back(next_fib);
        
        // Update n1 and n2 to their modded values
        n1 = n2;
        n2 = next_fib;
        
        // Check if we've returned to the starting pair (0, 1)
        if (pisanoseries[pisanoseries.size() - 1] == 1 && pisanoseries[pisanoseries.size() - 2] == 0) {
            // Remove the duplicate starting pair to get the actual cycle
            pisanoseries.pop_back();
            pisanoseries.pop_back();
            break;
        }
    }
    return pisanoseries;
}

int main() {
    ll n, m;
    cin >> n >> m;
    vector<ll> pisanoseries = pisano(m);
    ll location = n % pisanoseries.size();
    cout << pisanoseries[location] << endl;
    return 0;
}

What Changed? #

1. Corrected Termination Condition: Now we check if the last two elements are 0, 1 (matching the cycle start), which correctly identifies when the cycle has completed.
2. Modulo All Intermediate Values: We calculate next_fib as (n1 + n2) % m right away, and update n1 and n2 to these modded values. This keeps all numbers small, preventing overflow and ensuring every step of the calculation is accurate.
3. Minor Cleanup: Rearranged input handling in main() to be more intuitive, though the original order worked too.

For example, if you test with m=100 (which has a Pisano cycle length of 30), the fixed code will correctly generate the full cycle and compute F(n) mod 100 accurately, whereas your original code would return an incorrect cycle length.

内容的提问来源于stack exchange，提问作者vedant lodha