如何优化求n!十位个位数字的C++程序以解决OJ运行超时问题

原代码核心问题 #

• 计算逻辑冗余：题目只需要阶乘的十位和个位数字，原代码计算完整阶乘值，当输入n数值较大时，循环次数极多直接触发超时
• 整数溢出错误：int类型最大仅能存储12!的准确值，n≥13时数值溢出，不仅结果错误，溢出后的大数循环计算也会额外占用运行时间
• 未利用数学规律：当n≥15时，n!包含至少2个因子5和充足的因子2，乘积必然是100的倍数，末两位固定为00，无需循环计算

优化方案 #

核心优化点 #

1. 每次乘法运算后仅保留末两位结果，对100取模，完全避免溢出，同时降低计算量
2. 增加边界判断：n≥15时直接输出0 0，跳过所有循环逻辑
3. 最多仅需计算到14!的末两位，所有用例的计算时间固定为常数级，不会出现超时

优化后代码 #

#include <iostream>
using namespace std;

int main()
{
    int d, n;
    cin >> d;
    while(d--)
    {
        cin >> n;
        // n≥15时末两位固定为00
        if(n >= 15)
        {
            cout << "0 0\n";
            continue;
        }
        int last_two = 1;
        for(int i = 2; i <= n; i++)
        {
            // 仅保留末两位
            last_two = (last_two * i) % 100;
        }
        cout << last_two / 10 << " " << last_two % 10 << "\n";
    }
    return 0;
}

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