[已解决]数学问题

zhangjinxuan

众

所[

s]不[/s]周知，逆元主要是用来求解”已知 a mod p, b mod p 的值，求 (a/b) mod p 的值" 的问题。

做一个小改动，问题变成 ”已知 a mod p, b mod p 的值，求 (a mod b) % p 的值" 。

这个有没有解呢。

最佳答案

月排行榜 / 总排行榜

isdkz

2023-9-26 11:25:26

有解。



首先，我们知道 a mod p 和 b mod p 的值，可以表示成 a = kp + r1 和 b = mp + r2 的形式，其中 k、m 是整数，r1、r2 是余数，0 <= r1, r2 < p。



那么，我们可以将 a mod b 表示成 a mod b = (kp + r1) mod (mp + r2)。



根据模运算的性质，(kp + r1) mod (mp + r2) = ((kmp + mr1 + kp + r1) mod (mp + r2)) mod b。



因此，我们可以得到 a mod b 的值为 ((kmp + mr1 + kp + r1) mod (mp + r2)) mod p。



我们已知 r1、r2、p 的值，可以通过遍历 k、m 的值，计算出 (kmp + mr1 + kp + r1) mod (mp + r2) 的值，然后再对 p 取模即可得到最终的结果。

跳转到最佳答案楼层

isdkz

有解。



首先，我们知道 a mod p 和 b mod p 的值，可以表示成 a = kp + r1 和 b = mp + r2 的形式，其中 k、m 是整数，r1、r2 是余数，0 <= r1, r2 < p。



那么，我们可以将 a mod b 表示成 a mod b = (kp + r1) mod (mp + r2)。



根据模运算的性质，(kp + r1) mod (mp + r2) = ((kmp + mr1 + kp + r1) mod (mp + r2)) mod b。



因此，我们可以得到 a mod b 的值为 ((kmp + mr1 + kp + r1) mod (mp + r2)) mod p。



我们已知 r1、r2、p 的值，可以通过遍历 k、m 的值，计算出 (kmp + mr1 + kp + r1) mod (mp + r2) 的值，然后再对 p 取模即可得到最终的结果。

zhangjinxuan

isdkz 发表于 2023-9-26 11:25
有解。



首先，我们知道 a mod p 和 b mod p 的值，可以表示成 a = kp + r1 和 b = mp + r2 的形式，其 ...

《遍历k,m的值》

这说了就像说了似的