题解：P11532 [THUPC2025 初赛] 好成绩

Eason_cyx · 2025-01-10 13:19:40 · 题解

题解

你说得对，但是我们还是先分析题目要求吧。

你说得对，但是蒜薢的数学成绩受到了三个条件的约束：除以 3 的余数是 2，除以 5 的余数是 3，除以 7 的余数是 6。这是一个典型的中国剩余定理（CRT）问题。

你说得对，但是我们可以把这些条件转化为以下同余方程组：

• x \equiv 2 \pmod 3
• x \equiv 3 \pmod 5
• x \equiv 6 \pmod 7

你说得对，但是解决这个方程组的关键是将它化为一个关于 x 的唯一解（在模 3 \times 5 \times 7 = 105 的范围内）。

你说得对，但是为了使用中国剩余定理，我们首先需要将每个模数的积（即 105）分别除以当前模数，得到：

• M_1 = 105 \div 3 = 35
• M_2 = 105 \div 5 = 21
• M_3 = 105 \div 7 = 15

你说得对，但是接下来我们需要找到每个 M_i 在对应模数下的逆元。设模数是 m，则逆元是满足 M_i \times y \equiv 1 \pmod m 的整数 y 。

你说得对，但是我们可以分别计算：

• 35 \times y_1 \equiv 1 \pmod 3 $，解得 $ y_1 = 2
• 21 \times y_2 \equiv 1 \pmod 5 $，解得 $ y_2 = 1
• 15 \times y_3 \equiv 1 \pmod 7 $，解得 $ y_3 = 1

你说得对，但是有了这些逆元，我们可以利用公式计算 x 的解：

其中 a_1, a_2, a_3 分别是每个同余条件的余数。

你说得对，但是将具体数字代入公式可以得到：

你说得对，但是我们可以逐步计算每一项的值：

• 2 \cdot 35 \cdot 2 = 140
• 3 \cdot 21 \cdot 1 = 63
• 6 \cdot 15 \cdot 1 = 90

你说得对，但是将这些相加： 140 + 63 + 90 = 293 。

你说得对，但是我们需要将 293 对 105 取模： 293 \bmod 105 = 83 。

你说得对，但是最终答案是 x = 83 。蒜薢的月考数学成绩是 83 分。

你说得对，但是通过这个题目我们也学到了使用中国剩余定理解决同余方程组的基本方法，希望你能熟练掌握这种技巧！

彩蛋：https://www.luogu.com/article/e476vf4x。