鱼C论坛

 找回密码
 立即注册
查看: 1195|回复: 2

[已解决]数学问题

[复制链接]
发表于 2023-9-26 11:25:18 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 zhangjinxuan 于 2024-4-28 17:00 编辑






所[

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

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

这个有没有解呢。
最佳答案
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 取模即可得到最终的结果。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 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 取模即可得到最终的结果。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-9-26 11:28:02 | 显示全部楼层
isdkz 发表于 2023-9-26 11:25
有解。



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

《遍历k,m的值》

这说了就像说了似的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 23:52

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表