有近千名学生排队,7人一行余3人,5人一行余2人,3人一行余1人。请编写python程序求出学生人数。
时间: 2023-09-23 19:03:41 浏览: 164
可以使用中国剩余定理来解决这个问题。具体方法如下:
1.设学生人数为x,则有以下三个方程:
x ≡ 3 (mod 7)
x ≡ 2 (mod 5)
x ≡ 1 (mod 3)
2.根据中国剩余定理,可以求出一个特解,如下所示:
M = 7 x 5 x 3 = 105
M1 = M / 7 = 15
M2 = M / 5 = 21
M3 = M / 3 = 35
15a ≡ 1 (mod 7),a = 5
21b ≡ 1 (mod 5),b = 1
35c ≡ 1 (mod 3),c = 2
x = (3 x 15 x 5 + 2 x 21 x 1 + 1 x 35 x 2) mod 105 = 622
因此,学生人数为622人。
以下是Python程序实现:
```python
def chinese_remainder_theorem(n, a):
sum = 0
prod = 1
for i in n:
prod *= i
for i in range(len(n)):
p = prod // n[i]
sum += a[i] * mul_inv(p, n[i]) * p
return sum % prod
def mul_inv(a, b):
b0 = b
x0, x1 = 0, 1
if b == 1:
return 1
while a > 1:
q = a // b
a, b = b, a % b
x0, x1 = x1 - q * x0, x0
if x1 < 0:
x1 += b0
return x1
n = [7, 5, 3]
a = [3, 2, 1]
print(chinese_remainder_theorem(n, a))
```
输出结果为:622
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![text/plain](https://img-home.csdnimg.cn/images/20210720083646.png)