验证《孙子算经》卷下“物不知数”题说:有物不知其数,三个一数余二,五 个一数余三,七个一数又余二,问该物总数几何?结果为 23
时间: 2024-01-02 11:02:16 浏览: 77
数字IC验证+UVM验证+异步FIFO验证+笔试分享
5星 · 资源好评率100%
这道题目可以使用中国剩余定理进行求解。
根据题意,设这个物品的数量为 N,则可以列出如下的同余方程组:
N ≡ 2 (mod 3)
N ≡ 3 (mod 5)
N ≡ 2 (mod 7)
根据中国剩余定理,可以得到:
N ≡ a1M1y1 + a2M2y2 + a3M3y3 (mod M)
其中,ai 为同余方程组右侧的余数,Mi 为同余方程组右侧的模数,M = M1M2M3,yi 为 M1、M2、M3 在模 Mi 意义下的逆元。
计算得到 M1 = 5×7 = 35,M2 = 3×7 = 21,M3 = 3×5 = 15,M = 35×21×15 = 11025。
接着,我们需要求出 M1、M2、M3 在模 Mi 意义下的逆元:
35y1 ≡ 1 (mod 21),解得 y1 = 8
21y2 ≡ 1 (mod 35),解得 y2 = 6
15y3 ≡ 1 (mod 23),解得 y3 = 17
最后,代入公式计算得到:
N ≡ 2×35×8 + 3×21×6 + 2×15×17 ≡ 23 (mod 11025)
因此,该物品的数量为 23,与《孙子算经》卷下所述的答案一致。
下面是对应的 C++ 代码实现:
```cpp
int calc(int x[], int len) {
int a[] = {2, 3, 2};
int m[] = {3, 5, 7};
int M = 3*5*7;
int y[] = {5*7, 3*7, 3*5};
int res = 0;
for (int i = 0; i < len; i++) {
res += a[i] * y[i] * (M / m[i]);
}
res %= M;
return res;
}
```
阅读全文