题目:
输入n, 计算 S = 1! + 2!+3! + ... + n!的末6位(不含前导0)。n<= 10^6, n! 表示前n个正整数之积。
样例输入
10
样例输出:
37913
分析
核心算法
"for(int i=1;i<=n;i++) S+= i ! "
这个只是伪代码
实现一:
#include<stdio.h>
int main()
{
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 *= j;
}
S += factorial;
printf("i:%d factorial:%d S:%d \n",i,factorial,S);
}
printf("%d\n",S%1000000);
return 0;
}
//当输入100时,就会溢出
实现2:
在实现1中会存在溢出的问题。
这里利用数学知识,
要计算只包含加法、减法和乘法的整数表达式除以正整数n的余数,可以在每步计算之后对n取余,结果不变。
#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("i:%d factorial:%d S:%d\n",i,factorial,S);
}
printf("%d\n",S);
printf("Time used = %.2f\n",(double)clock()/CLOCKS_PER_SEC);
return 0;
}
//利用数学中的知识
//要计算只包含加法、减法、和乘法的整数表达式除以正整数n的余数,可以 在每步计算之后对n取余,结果不变。
//计时函数 clock(),返回程序目前为止运行的时间。
//这个时间处理常数CLOCKS_PER_SEC之后,得到的值以秒为单位。
//clock() 不要直接使用,应总是除以 CLOCKS_PER_SEC