每日一道c++计算题：阶乘之和
问题：输入n，计算S=1!+2!+3!+…+n!的末6位(不含前导0)。n≤10的6次方， n!表示前n个正整数之积。
#include
using namespace std;
int main()
{
int n;
cin >> n;
long long factorial = 1;
long long sum = 0;
const int MOD = 1000000;
for (int i = 1; i <= n; ++i) {
factorial = (factorial * i) % MOD;
sum = (sum + factorial) % MOD;
}
cout << sum << endl;
return 0;
}
阶乘的性质：随着 n 的增大，阶乘 n! 会迅速增大。当 n \geq 20 时， n! 的值会超过 10^{18} ，但由于我们只需要末 6 位，因此可以利用模运算的性质： (ab) % 1000000 = [(a % 1000000)(b % 1000000)] % 1000000 。优化计算：对于每个阶乘 i! ，可以在计算过程中对 1000000 取模，这样可以避免数值过大，同时保证结果的末 6 位正确。求和取模：在计算阶乘之和时，同样对 1000000 取模，确保结果始终是末 6 位。
那么模运算的性质是怎么来的呢？
模运算的基本定义
对于整数 a （被除数）、 b （除数，b>0 ），根据整数除法的定义，存在唯一的整数 q （商）和 r （余数），使得： a = b * q + r ，其中 0<=r < b ，而 a mod b = r ，这就是模运算（取余运算）的基本定义，余数 r 是除法运算后剩下的小于除数的非负整数部分。
模运算的基本性质推导
（1）(a + b) mod m = [(a mod m) + (b mod m)] mod m
设 a = m * q1 + r1 ，其中 0<= r1 < m ，所以 a mod m = r1 ；
设 b = m * q2 + r2 ，其中 0 <=r2 < m ，所以 b mod m = r2 。那么 a + b = m *q1 + r1 + m * q2 + r2 = m * (q1 + q2) + (r1 + r2) 。现在看 (r1 + r2) 与 m 的关系：如果 r1 + r2 < m ，那么 (a + b) mod m = r1 + r2 = (a mod m) + (b mod m) ，而 [(a mod m) + (b mod m)] mod m = (r1 + r2) mod m = r1 + r2 等式成立。如果 r1 + r2 >= m ，设 r1 + r2 = m * q3 + r3 ，其中 0 <=r3 < m ，那么 a + b = m * (q1 + q2 + q3) + r3 ，所以 (a + b) mod m = r3 ；而 [(a mod m) + (b mod m)] mod m = (r1 + r2) mod m = r3 ，等式也成立。
综上，(a + b) mod m = [(a mod m) + (b mod m)] mod m 这个性质得证，它体现了模运算对加法的“分配性”（在取模意义下 ）。
（2）(a * b) mod m = [(a mod m) * (b mod m)] mod m
同样基于前面的设定， a = m * q1 + r1 ， b = m * q2 + r2 ，其中 0 <=r1, r2 < m 。
计算 a * b ：
a * b = (m* q1 + r1) * (m * q2 + r2)
= m * q1 *m * q2 + m *q1 * r2 + m * q2 * r1 + r1 * r2
= m *(m *q1 *q2 + q1 * r2 + q2 * r1) + r1 * r2
可以看到， a * b 表示成了 m * k + (r1 * r2) 的形式（其中 k = m * q1 * q2 + q1 *r2 + q2 * r1 是整数 ）。根据模运算定义， (a * b) mod m = (r1 * r2) mod m ，而 (r1 * r2) 就是 (a mod m) * (b mod m) ，所以 (a * b) mod m = [(a mod m) * (b mod m)] mod m ，这就是模运算对乘法的“分配性”，也是你在计算阶乘之和取模时用到的关键性质，利用它可以在每一步乘法后取模，避免数值过大。
（3）a mod m = (a + k * m) mod m（ k 为整数 ）
因为 a + k * m = m * (q + k) + r （结合 a = m * q + r 来看 ），根据模运算定义，它除以 m 的余数依然是 r ，所以 a mod m = (a + k * m) mod m 。这说明一个数加上或减去 m 的整数倍，其模 m 的余数不变，也常用来简化计算，比如计算很大的数的模，可以先减去 m 的若干倍，让数值变小后再取模。
模运算性质在实际编程中的意义
像你之前计算阶乘之和取末 6 位（即模 1000000 ），就用到了乘法模运算的性质。因为阶乘随着 n 增大增长极快，直接计算完整的阶乘数值会超出数据类型能表示的范围（比如 int 、 long long 等 ），但利用 (a * b) mod m = [(a mod m) * (b mod m)] mod m ，每一步计算阶乘时都对 1000000 取模，这样数值就会被限制在一定范围内，既不会溢出，又能保证最终结果的末 6 位是正确的。
简而言之，模运算的这些性质源于整数除法中余数的定义，通过对整数进行分解和推导得到，而在编程处理大数相关的取余计算（如阶乘、幂运算取模等场景 ）时，这些性质能帮我们高效且正确地得到结果，避免数值溢出等问题 。