博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
通过逆元实现大数据除法的取模
阅读量:5878 次
发布时间:2019-06-19

本文共 960 字,大约阅读时间需要 3 分钟。

当题目中数据较大,而且计算中出现过除法的时候。往往取模会出错

当计算 (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为整数,p为素数,则可写出同余方程a^(p-1)≡1(mod p)
故a*a^(p-2)≡1(mod p),a^(p-2)是a的逆元。
一个快速幂搞定。

 

 

 

转载于:https://www.cnblogs.com/ffhy/p/6013262.html

你可能感兴趣的文章
51nod 1292 字符串中的最大值V2(后缀自动机)
查看>>
加快ALTER TABLE 操作速度
查看>>
学习笔记之软考数据库系统工程师教程(第一版)
查看>>
基本网络概念
查看>>
将 ASP.NET Core 2.0 项目升级至 ASP.NET Core 2.1 RC 1
查看>>
js提交图片转换为base64
查看>>
学习CodeIgniter框架之旅(二)继承自定义类
查看>>
Y2161 Hibernate第三次考试 2016年8月18日 试卷分析
查看>>
Angular CLI 使用教程指南参考
查看>>
PHP 程序员的技术成长规划
查看>>
用于守护进程的出错处理函数
查看>>
memcached 分布式聚类算法
查看>>
禁止body滚动允许div滚动防微信露底
查看>>
Xtreme8.0 - Kabloom dp
查看>>
jquery css3问卷答题卡翻页动画效果
查看>>
MDK5.00中*** error 65: access violation at 0xFFFFFFFC : no 'write' permission的一种解决方法
查看>>
Android 集成支付宝支付详解
查看>>
SQL分布式查询、跨数据库查询
查看>>
C#------连接SQLServer和MySQL字符串
查看>>
Arcgis Licensemanager 不能启动的原因之一(转载)
查看>>