[数据结构与算法]信息学奥赛一本通 2033：【例4.19】阶乘之和

【题目链接】

ybt 2033：【例4.19】阶乘之和

【题目考点】

1. 同余定理

根据同余定理，有：
$(a?b)\%m=(a\%m?b\%m)\%m$
$(a+b)\%m=(a\%m+b\%m)\%m$

2. 循环嵌套

3. 阶乘

n的阶乘为$n!=1?2?...?n$
实现函数如下：

int fact(int n)
{
	int s = 1;
	for(int i = 1; i <= n; ++i)
		s *= i;
	return s;
}

【解题思路】

• 一个直接的思路是：求出每个数的阶乘，加和，而后对M取模(设M的值为1000000)，就可以得到结果的末6位。但阶乘的结果很大，会超出int以及long long类型可以表示的数字范围，所以必须一边计算一边取模。
  $ans=1!+2!+...+n!$
  根据同余定理，有：
  $ans\%M=(1!\%M+2!\%M+...+n!\%M)\%M$
  $n!\%M=(n\%M?(n?1)!\%M)\%M$
  可以先求每个阶乘模M的值，然后将这些结果加起来，一边加一边对M取模，即可。
• 如果分别对每个数值求阶乘，需要做n次阶乘，每次阶乘的复杂度是$O(n)$，总体复杂度是$O(n^2)$，而本问题n达到$10^6$，$O(n^2)$会超时。
• 考虑到当$n\le M$时：$n!\%M=(n?(n?1)!\%M)\%M$，我们可以借助上一次的阶乘结果$(n?1)!\%M$，乘上数字n再对M取模，即可得到$n!\%M$。这样求每个阶乘的复杂度是$O(1)$，总体复杂度是$O(n)$，可以通过。

【题解代码】

解法1：

#include<bits/stdc++.h>
using namespace	std;
#define M 1000000 //设置常量，下面M就是1000000
int	main()
{
	int n, num = 1, sum = 0;//num：阶乘%M sum：阶乘和%M 
	cin >> n;
	for(int i = 1; i <= n; ++i)
	{
		num = num * i % M;
		sum = (sum + num) % M;
	}
	cout << sum;
	return 0;
}