求阶乘之和

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

样例输入：

10

样例输出：

37913

法一：

#include

int main() {
	const int Y = 1000000;
	int sum = 0, n = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int num = 1;
		for (int j = 1; j <= i; j++) {
			num = j * num % Y;
		}
		sum = (sum + num) % Y; // 这里每步都取余是怕数据溢出
//计算只包含加法、减法、乘法的整数表达式除以正整数n的余数，可以在每步计算后对n取余，结果不变的
	}
	printf("%d\n", sum);
	return 0;
}

法一的解法当然可以，但是当n之过大时效率会很低，估计到n = 10^6时，程序所需要的时间估计会达到几十分钟，所以有了法二。

法二：

法二是将法一优化之后，不再担心效率和溢出的问题

在这里我们先用clock()函数（我在专栏C/C++算法自学小记中有提到）来了解整个程序的运行时间

#include
#include

int main() {
	const int Y = 1000000;
	int sum = 0, n = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int num = 1;
		for (int j = 1; j <= i; j++) {
			num = j * num % Y;
		}
		sum = (sum + num) % Y;
	}
	printf("%d\n", sum);
	printf("用时：%.2f\n", (double)clock()/CLOCKS_PER_SEC);
	return 0;
}

    

 这里用clock()函数统计用时有一定的误差，因为在输入n值时也会算时间，当你运行程序后，你打个扑克再来输入n，用时可能就有点久了，当然这也看个人体质。

到这里我们发现n在20~40一定有个n！末尾是6个0，不然后面的答案也不会始终不变了。

 

#include

int main() {
	const int Y = 1000000;
	int sum = 0, n = 40,i = 1;
	for (i = 1; i <= n; i++) {
		int num = 1;
		for (int j = 1; j <= i; j++) {
			num = j * num % Y;
		}
		if(num % Y == 0) break;
	}
	printf("%d\n", i);
	return 0;
}

 输出可知当n = 25 时n！的末六位为零，所以将代码修改如下即为法二

#include
#include 

int main() {
	const int Y = 1000000;
	int sum = 0, n = 0;
	scanf("%d", &n);
	if(n>25) n = 25; 
	for (int i = 1; i <= n; i++) {
		int num = 1;
		for (int j = 1; j <= i; j++) {
			num = j * num % Y;
		}
		sum = (sum + num) % Y;
	}
	printf("%d\n", sum);
	printf("用时：%.2f\n", (double)clock() / CLOCKS_PER_SEC);
	return 0;
}

  附图

 

即使n为10^6时用时还是不久 。