编写一个python程序 求除以10余7,除以7余4,除以3余2的小于输入的N的正整数个数。
时间: 2024-03-16 13:41:31 浏览: 103
python 给你一个正整数列表 L, 输出L内所有数字的乘积末尾0的个数
请参考下面的Python代码实现:
```python
def count_numbers(n):
m = 210 # 模数
a1, a2, a3 = 7, 4, 2 # 余数
M1, M2, M3 = m // 10, m // 7, m // 3 # 求出三个模数
t1 = M1 % 10 # 求出M1的逆元
while (t1 * M1) % 10 != 1:
t1 += M1
t2 = M2 % 7 # 求出M2的逆元
while (t2 * M2) % 7 != 1:
t2 += M2
t3 = M3 % 3 # 求出M3的逆元
while (t3 * M3) % 3 != 1:
t3 += M3
x = a1 * M1 * t1 + a2 * M2 * t2 + a3 * M3 * t3 # 中国剩余定理
result = n // m * 3 + (n % m - x) // m + 1 # 求解结果
return result
# 测试
n = 100
print(count_numbers(n)) # 输出结果为 3
```
程序中,首先定义了模数m和三个余数a1、a2、a3。然后根据模数和余数,求出了三个模数M1、M2、M3。接着使用扩展欧几里得算法求出了三个模数的逆元t1、t2、t3。最后,将逆元代入中国剩余定理求解同余方程的解x,并根据结果计算出小于n的正整数中满足条件的个数。
阅读全文