求除以10余7,除以7余4,除以3余2的小于输入的N的正整数个数。
时间: 2024-04-07 07:32:01 浏览: 134
这是一个数学问题,需要使用中国剩余定理进行求解。
首先根据题意可以列出如下方程组:
x ≡ 7 (mod 10)
x ≡ 4 (mod 7)
x ≡ 2 (mod 3)
根据中国剩余定理,可以将上述方程组化为一个同余方程:
x ≡ a1M1y1 + a2M2y2 + a3M3y3 (mod M)
其中,M = 10 × 7 × 3 = 210,M1 = 21,M2 = 30,M3 = 70,且M1、M2、M3两两互质。
令b1 = M1y1,b2 = M2y2,b3 = M3y3,则可以得到:
b1 ≡ 1 (mod 21),b1 ≡ 0 (mod 30),b1 ≡ 0 (mod 70)
b2 ≡ 0 (mod 21),b2 ≡ 1 (mod 30),b2 ≡ 0 (mod 70)
b3 ≡ 0 (mod 21),b3 ≡ 0 (mod 30),b3 ≡ 1 (mod 70)
根据扩展欧几里得算法,可以求出b1、b2、b3的值为:
b1 = 71,b2 = -49,b3 = -19
代入同余方程,可以得到:
x ≡ 7 × 71 + 4 × (-49) + 2 × (-19) (mod 210)
化简后,得到:
x ≡ 129 (mod 210)
因此,小于输入的N的正整数中满足要求的个数为:
⌊N/210⌋ × 3 + [(N mod 210) - 129] / 210
其中,⌊N/210⌋表示N除以210的整数部分。
相关问题
编写一个python程序,计算除以10余7,除以7余4,除以3余2的小于输入n的正整数个数
好的,以下是实现该功能的 Python 程序:
```python
def count_nums(n):
count = 0
for i in range(1, n):
if i % 10 == 7 and i % 7 == 4 and i % 3 == 2:
count += 1
return count
n = int(input("请输入一个正整数:"))
print("小于", n, "的正整数中满足要求的个数为:", count_nums(n))
```
程序的逻辑很简单,就是用一个循环遍历小于输入值 n 的所有正整数,然后判断每个数是否同时满足三个条件,如果满足,则计数器加一。最后输出满足条件的个数即可。
阅读全文