阶乘非零位算法与菜价系统实现详解

1. 阶乘最后的非零位：算法优化与实现详解

1.1 问题背景与数学原理

阶乘运算在数学和计算机科学中具有重要地位。N的阶乘（记作N!）定义为所有小于等于N的正整数的乘积。随着N的增大，阶乘值呈爆炸式增长——13!就需要32位整数存储，而70!的数值已经超出了常规浮点数的表示范围。

计算阶乘最后的非零位看似简单，实则暗藏玄机。直接计算整个阶乘再取末位的方法对于小数值可行，但当N>20时就会面临数值溢出的问题。因此，我们需要更聪明的数学方法来解决这个问题。

关键数学原理：

• 阶乘末尾的0由因子2和5的配对产生
• 每对2和5会产生一个10，从而在末尾添加一个0
• 在阶乘中，2的因子数量总是多于5的因子数量
• 去掉所有2-5对后，剩下的2的因子数量为count2-count5

1.2 高效算法设计与实现

基于上述原理，我们可以设计如下算法：

1. 初始化result=1，count2=0，count5=0
2. 对于i从1到N：
   a. 分解i的质因数，统计2和5的个数
   b. 将i中所有2和5因子去除后，乘以result并对大数取模
3. 计算多余的2的个数：diff = count2 - count5
4. 将多余的2乘回result
5. 去除result末尾可能剩余的0
6. 返回result的最后一位

cpp复制#include <iostream>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    int result = 1;
    int count2 = 0, count5 = 0; 
    
    for (int i = 1; i <= N; ++i) {
        int num = i;
        
        // 统计2的因子数量
        while (num % 2 == 0) {
            count2++;
            num /= 2;
        }
        
        // 统计5的因子数量
        while (num % 5 == 0) {
            count5++;
            num /= 5;
        }
        
        // 乘以剩余部分并取模防止溢出
        result = (result * num) % 1000000;
    }
    
    // 处理多余的2
    int diff = count2 - count5;
    for (int i = 0; i < diff; ++i) {
        result = (result * 2) % 1000000;
    }
    
    // 去除末尾可能的0
    while (result % 10 == 0) {
        result /= 10;
    }
    
    cout << result % 10 << endl;
    
    return 0;
}

1.3 算法优化与注意事项