阶乘之和

描述

输入n，计算S=1！+2！+3！+4！+······+n！的末6位（不包前导0）。n<=10^6,n!表示前n个正整数之积。

输入

10

输出

37913

分析

首先因为只要末6位，所以输出时对10^6取模。但n的数值很大，如果直接进行阶乘再取模，仍然有会溢出。所以我们可以对每一步计算进行取模结果不变（存在：要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数，可以在每一步计算之后对取余，结果不变）。但即使是这样，当n的值很大时，需要进行的运算时间就十分的长，所以我们需要找出规律，进行优化。因为25！末尾有6个0，所以从25开始，后面所有项都不会影响和的末6位——只需要在程序的前面加一条语句“if(n>25) n=25;”,效率和溢出都将不存在问题。

代码演示

/* *阶乘之和 */ #include<iostream> #include<time.h> using namespace std; int main() { const int MOD = 1000000; int n, S = 0; cin >> 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; } cout << S << endl; cout << "Time used=" << (double)clock() / CLOCKS_PER_SEC << endl;//clock（）函数可以获得整个程序的运行时间，这个时间除以常数CLOCKS_PER_SEC之后得到的值以“秒“为单位。 return 0; }