C++实现的Pisano周期生成器处理三位数周期时结果错误

你的代码在处理小周期时运行正常，但遇到稍大的m（比如25）就返回错误结果，核心问题出在未对斐波那契数取模导致数值溢出，以及判断逻辑的隐含风险。

问题分析 #

• 数值溢出：你直接计算完整的斐波那契数cur2，但斐波那契数增长极快——第90项左右就会超过long long的最大值（约9e18）。当m=25时，周期是100，计算到第100项时cur2早已溢出，变成错误的负数或乱码，导致后续的cur2 % m结果完全不正确，无法触发终止条件，循环会一直跑下去直到偶然满足错误的判断。
• 判断逻辑冗余：你用prev1和cur1保存初始的0和1来判断循环终止，但其实可以直接在迭代过程中检查是否回到了(0, 1)的初始状态，这样更直观且不易出错。

修复后的代码 #

#include <iostream>
using namespace std;

long long pisano_period(long long m) {
    if (m == 1) return 1; // 特殊情况：模1所有数都是0，周期为1
    long long a = 0, b = 1;
    long long period = 0;
    do {
        long long c = (a + b) % m;
        a = b;
        b = c;
        period++;
    } while (!(a == 0 && b == 1));
    return period;
}

int main() {
    long long m;
    cin >> m;
    cout << pisano_period(m) << endl;
    return 0;
}

关键改进点 #

• 每次迭代取模：计算新的斐波那契数时直接对m取模，这样a和b的值始终在[0, m-1]范围内，永远不会溢出，保证取模结果的正确性。
• 直接判断初始状态：循环终止条件设为回到a=0且b=1，这完全符合Pisano周期的定义——当模m的斐波那契序列再次出现初始的0和1时，整个周期就完成了。
• 特殊情况处理：针对m=1的情况单独处理，因为所有数模1都是0，周期为1。

测试你的例子：

• 输入24，返回24（正确）
• 输入25，返回100（正确）

内容的提问来源于stack exchange，提问作者Rahul Vishal Mishra