用python求一个100以内的数,除以3余2,除以5余3,除以7余2
时间: 2024-05-12 19:21:03 浏览: 4
题目分析:
根据题目所给的条件,我们可以列出如下方程组:
$$
\begin{cases}
x \equiv 2 \pmod{3} \\
x \equiv 3 \pmod{5} \\
x \equiv 2 \pmod{7}
\end{cases}
$$
其中,$x$ 为所求的数。
解题思路:
根据中国剩余定理,我们可以将上述方程组转化为:
$$
x \equiv a_1 \pmod {m_1} \\
x \equiv a_2 \pmod {m_2} \\
x \equiv a_3 \pmod {m_3}
$$
其中,$m_1 = 3$,$m_2 = 5$,$m_3 = 7$,$a_1 = 2$,$a_2 = 3$,$a_3 = 2$。
根据扩展欧几里得算法,我们可以求出:
$$
\begin{cases}
M_1 = m_2 \cdot m_3 = 35 \\
M_2 = m_1 \cdot m_3 = 21 \\
M_3 = m_1 \cdot m_2 = 15
\end{cases}
$$
再分别求出它们在模 $m_i$ 意义下的乘法逆元 $t_i$,即:
$$
\begin{cases}
t_1 \equiv 1 \pmod {m_1} \\
t_1 \equiv 0 \pmod {m_2} \\
t_1 \equiv 0 \pmod {m_3}
\end{cases}
\Rightarrow t_1 = 1
$$
$$
\begin{cases}
t_2 \equiv 0 \pmod {m_1} \\
t_2 \equiv 1 \pmod {m_2} \\
t_2 \equiv 0 \pmod {m_3}
\end{cases}
\Rightarrow t_2 = 2
$$
$$
\begin{cases}
t_3 \equiv 0 \pmod {m_1} \\
t_3 \equiv 0 \pmod {m_2} \\
t_3 \equiv 1 \pmod {m_3}
\end{cases}
\Rightarrow t_3 = 1
$$
最终的解为:
$$
x \equiv \sum\limits_{i=1}^3 a_i \cdot M_i \cdot t_i \pmod {M_1} = 23
$$
代码实现:
```python
def chinese_remainder_theorem(a, m):
"""
扩展欧几里得算法求逆元
"""
def ext_gcd(a, b):
if b == 0:
return 1, 0
x, y = ext_gcd(b, a % b)
return y, x - a // b * y
# 求 M1, M2, M3
M1 = m[1] * m[2]
M2 = m[0] * m[2]
M3 = m[0] * m[1]
# 求 t1, t2, t3
t1 = 1
t2 = ext_gcd(M2, m[0])[0]
t3 = ext_gcd(M3, m[0])[0]
# 求 x
x = (a[0] * M1 * t1 + a[1] * M2 * t2 + a[2] * M3 * t3) % (m[0] * m[1] * m[2])
return x
# 测试
a = [2, 3, 2]
m = [3, 5, 7]
x = chinese_remainder_theorem(a, m)
print(x) # 输出 23
```