题目:
输入 n , 计算 S = 1! + 2! + 3! + ...+ n! 的末 6 位 (不含前导 0). n <= 10^6, n! 表示前 n 个正整数之积.
样例输入:
10
样例输出:
37913
思路:
用一个累加器 sum 来记录总和, 用 term 来表示每一项的阶乘.
第一种方法是用二重循环, 中规中矩的算法.
第二种方法, 观察可知, 后一项的值等于前一项乘当前项序号, 于是每次能够利用前面已经算出的阶乘结果, 这样就能避免二重循环.
还需注意, 在大数做乘法时的溢出问题. 解决方法: 在每次计算完当前项结果之后, 马上进行取模, 再每次累加之后, 迅速对 sum 也进行取模.
代码:
- #include <iostream>
- using namespace std;
- int main()
- {
- const int MOD = 1000000;
- int sum = 0, n = 0;
- cin>> n;
- for (int i = 1; i <= n; ++i) {
- int static term = 1;
- term *= i;
- sum += (term % MOD);
- }
- cout << sum % MOD << endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3355898.html