首页 > 代码库 > 通过逆元实现大数据除法的取模
通过逆元实现大数据除法的取模
当题目中数据较大，而且计算中出现过除法的时候。往往取模会出错
当计算 （A/B) % c 等价于 （A*B1)% c
其中 B1 是 B 的逆元。
那么逆元如何求呢。
先给出逆元的定义
a*x ≡1 （mod n) ，如果x是方程的解，则x称作 a 关于模 n 的逆。
a的逆元存在是有条件的： 方程ax-ny==1 要有解 则 1必须是gcd（a,n)的倍数 ，因此，a和n必须素质，
即 gcd（a,n)==1 在这个前提下 ax≡1（mod n) 只有唯一解。
现在我们来证明上面的结论：用若b*b1 % c == 1，则( a/b ) % c ！= ( a*b1 ) % c
若我们证明这一命题是错误的，我们目的就达到了。
令，a/b == k1*c+y1
a*b1 == k2*c+y2
原来的证明则变成了：若b*b1 % c == 1，则 y1!=y2
两式相减，有 a/b-a*b1 == (k1-k2)*c + (y1-y2)
设 k == k1-k2
y == y1-y2
有，a/b-a*b1 == k*c + y
左右乘以b，有 a*(1-b*b1) == k*b*c + b*y
左右模上c，
左边 == a*(1-b*b1)%c
== ( a*( 1%c - b*b1%c ) )%c
== 0
右边 == (k*b*c + b*y)%c
== b*y%c
因为a/b为整除，b显然不会是0，那么y必须是0，这与命题矛盾，证毕
为什么求逆元会用扩展欧几里得？
我们的目标，其实是解b*b1 % c == 1
令 b*b1 == k*c + 1
即 -k*c + b*b1 == 1
仔细观察，这个不就是扩展欧几里得嘛。
那么，为什么gcd(b,c)==1，才会有逆元变得简单了。
因为 1 % gcd(b,c) == 0 ，扩展欧几里得才有解，具体来说，gcd(b,c)只能为1
令，a/b == k1*c+y1
a*b1 == k2*c+y2
原来的证明则变成了：若b*b1 % c == 1，则 y1!=y2
两式相减，有 a/b-a*b1 == (k1-k2)*c + (y1-y2)
设 k == k1-k2
y == y1-y2
有，a/b-a*b1 == k*c + y
左右乘以b，有 a*(1-b*b1) == k*b*c + b*y
左右模上c，
左边 == a*(1-b*b1)%c
== ( a*( 1%c - b*b1%c ) )%c
== 0
右边 == (k*b*c + b*y)%c
== b*y%c
因为a/b为整除，b显然不会是0，那么y必须是0，这与命题矛盾，证毕
为什么求逆元会用扩展欧几里得？
我们的目标，其实是解b*b1 % c == 1
令 b*b1 == k*c + 1
即 -k*c + b*b1 == 1
仔细观察，这个不就是扩展欧几里得嘛。
那么，为什么gcd(b,c)==1，才会有逆元变得简单了。
因为 1 % gcd(b,c) == 0 ，扩展欧几里得才有解，具体来说，gcd(b,c)只能为1
其实还有一种比较优的方法（快速幂，费马小定理）
费马小定理：是若a为整数，p为素数，则可写出同余方程a^(p-1)≡1(mod p)
故a*a^(p-2)≡1(mod p)，a^(p-2)是a的逆元。
一个快速幂搞定。
通过逆元实现大数据除法的取模
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。