中途取模为什么对结果没有影响

Question

今天写代码看见一个操作

while(b -- ){
    t = (t*a + 1) % mod;
}

mod是一个常量。题目要求的是对最终结果进行取模，但它在中途就进行取模了，我看有人说是为了防止溢出，因为这数很大。但我想知道为什么中途取模和最终结果取模答案一样。本人数学不太好，没有想明白，来此请教，希望有人可以仔细回答，谢谢！

Answer 1

一心只想AC 上午好☀️☀️☀️️
本答案参考ChatGPT-3.5

在这个代码中，每次循环都执行了 (t*a + 1) % mod 这个操作，即每次都对 (t*a + 1) 进行取模。而最后的结果需要对最终的 t 进行取模。

为什么中途取模和最终结果取模答案一样呢？

这是因为取模操作具有一个重要的性质：(a + b) % c = ((a % c) + (b % c)) % c。也就是说，如果我们对 (t*a + 1) 进行取模得到的结果再对 mod 取模，和直接对 (t*a + 1) 和 mod 分别取模再进行计算得到的结果是一样的。

所以，无论是在中途进行取模，还是在最终结果中进行取模，得到的结果都是一样的。

为什么要在中途进行取模？

其中一个原因是避免溢出。由于 (t*a + 1) 和 mod 都是很大的数，如果不进行取模，可能会导致乘法操作的结果超出计算机所能表示的范围，从而产生溢出。

另外，中途进行取模可以保持计算结果的范围在相对较小的值内，从而在计算过程中减小数值的大小，提高计算效率。

所以，中途取模的操作在防止溢出和提高计算效率方面都有一定的作用。

以下是修改后的代码：

while(b-- ){
    t = (t*a + 1) % mod;
}
result = t % mod;  // 对最终的结果进行取模

注意，这里需要将最终的结果再次进行取模，以满足题目要求对最终结果进行取模的条件。