2.3 循环的代价
例题2-4 阶乘之和
输入n,计算S=1!+2!+3!+…+n!的末6位(不含前导0)。n≤106,n!表示 前n个正整数之积。
样例输入:
10
样例输出:
37913
提示
- 要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数,可以在 每步计算之后对n取余,结果不变。
- 计时函数clock()。该函数返回程序目前为止运行 的时间.这样,在程序结束之前调用此函数,便可获得整个程序的运行时间。这个时间除以常数CLOCKS_PER_SEC之后得到的值以“秒”为单位。
- 可以使用time.h和clock()函数获得程序运行时间。常数 CLOCKS_PER_SEC和操作系统相关,请不要直接使用clock()的返回值,而应总是除以 CLOCKS_PER_SEC。
- 。为了 避免输入数据的时间影响测试结果,可使用一种称为“管道”的小技巧:在Windows命令行下 执行echo 20|abc,操作系统会自动把20输入,其中abc是程序名(8)。
#include<stdio.h>
#include<time.h>
int main()
{
const int MOD = 1000000;
int n, S = 0; scanf("%d", &n);
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 = %.2f\n", (double)clock() / CLOCKS_PER_SEC);
return 0;
}
25!末尾有6个0,所以从第5项开始,后面的所有项都不会影响和的末6位数字——只需要在 程序的最前面加一条语句“if(n>25)n=25;”,效率和溢出都将不存在问题。