阶乘取模

我的算法日常 — 超大的阶乘取模

描述

• 输入n < 10**6
• 求1!+2!+…..n! 对1000000的模

思路

• 首先n特别大,容易超时
• 阶乘特别大那就每次都对1000000取模,阶乘时和最后相加都进行取模操作
• 试着找规律,25!的后六位均为零,所以25之后的阶乘都将无法影响最后结果的后六位

实现C代码

#include<stdio.h>   

#include<time.h>   //时间头文件    

int main()  
{  
    const int MOD = 1000000;  
    int n, S = 0;  
    scanf("%d", &n);  
    if(n > 25) n = 25;  

    for(int i = 1;i <= n;i ++)  
    {  
        int factorial = 1;  
        for(int j = 1;j <= i;j ++)  
        {  
            factorial = (factorial * j) % MOD;  
        }  
        S = (S + factorial) % MOD;  
    }  

    printf("%d\n", S);  
    printf("Time used = % 0.2f\n", (double)clock() / CLOCKS_PER_SEC); //时间除以常数的单位才是秒  

    return 0;  
}  

收获的小技巧

• 这种特别大的输入一般都有规律,可以试着去多输入几组,寻找规律
• 命令行的管道输入"echo 输入数据|程序名"可以消除输入数据所消耗的时间,从而的到程序处理数据的实际时间