书店网站建设策划书总结,龙岗建站费用,西安做网站招聘,使用帝国备份王搬迁织梦网站文章目录引言逆元费马小定理内容应用证明线性求逆元thanks for reading#xff01;引言
我们做题时经常会由于答案过大#xff0c;被要求使答案对一个质数取模 我们都知道#xff0c;加和乘对取模是没有影响的 减法也只需要写一个#xff1a;
int mod_minus(int a,int b)…
文章目录引言逆元费马小定理内容应用证明线性求逆元thanks for reading引言
我们做题时经常会由于答案过大被要求使答案对一个质数取模 我们都知道加和乘对取模是没有影响的 减法也只需要写一个
int mod_minus(int a,int b){return a-b0 ? a-b : a-bmod}就可以啦 但是除法就很头疼 怎么办呢 这里介绍一种比较简单的利用费马小定理求逆元实现取模除法的途径 结合快速幂每次复杂度为log级别 除此之外还会介绍一种线性求逆元的方法 首先我们先要搞清楚什么是逆元和费马小定理
逆元 乘法逆元是指数学领域群G中任意一个元素a都在G中有唯一的逆元a’具有性质a×a’a’×ae其中e为该群的单位元。——《百度百科》 通俗点说就是逆元与本身相乘等于1 逆元有一个性质 除一个数等于乘这个数的逆元 比如在正常的乘法意义下a/ba*(1/b) 这也是我们实现取模除法的关键 也就是说当我们要模质数p的条件下使答案除以一个数x时我们只需要乘上x在模p意义下的逆元即可 所以我们要求出这个逆元也就是要找到一个k使 x*k1mod p 怎么求呢 我们就要请出我们的费马小定理啦
费马小定理
内容
若p为质数且a、p互质则—— ap-11(mod p) 应用
讨论完逆元之后 这个定理怎么用就很显然啦 首先a若不与p互质那一定是p的质数乘完肯定是0 不互质时结合前面逆元的式子我们就可以有 k*a1ap-1 这样就可以得到k kap-2 如果你只是想背结论那么到这里你就已经下课了 不过背来的终究会忘推出来才是自己的 虽然证明也可能会忘 下面就是最好玩的证明了~
证明
我们只需要证明一下费马小定理其他就都是自己推的了 怎么证呢 引入概念 完全剩余系从模n的每个剩余类中各取一个数得到一个由n个数组成的集合叫做模n的一个完全剩余系 这玩意有啥用 别着急慢慢看 我们还需要一个引理 对于互质的a、p, 若i jmod p则a∗*∗i ! a∗*∗j (mod p) 这个为什么怎么证 看起来就是要反证啦 假设aiaj(mod p) 移一下项 a(i-j)0(mod p) 又因为a、p互质a mod p不可能为0 所以 i-j0mod p 这与i jmod p矛盾 证毕
有了完全剩余系和这个引理我们可以干一些东西了 先构造一个完全剩余系A A{0,1,2…p-1} 然后我们令每一项乘上一个a得到集合B B{0,a,2a,3a,…(p-1)a} 因为a与p互质A又是完全剩余系其中的数模p互不相同 由刚才的引理可知B中的元素模p也互不相同又因为B中也有p个数所以B也是一个模p的完全剩余系 然后我们又有一个很显然的结论 若ab (mod p),cd(mod p),那么 a∗*∗c b∗*∗d(mod p) 这个很好证了把每个数拆成k∗*∗px即可 所以我们把去掉模p0的数后的A的所有数乘起来B的所有数乘起来它们得到的乘积还是关于p同余的 写一下就是 p-1ap-1∗*∗(p-1)!(mod p) 移一下项就是 (p-1)!∗*∗ ap-1-10(mod p) 因为p是质数所以(p-1)!显然模p不等于0 所以 ap-1-10(mod p) 也就是 ap-11(mod p) 证毕
线性求逆元
洛谷传送门 如何在线性的时间复杂度求出[1,n]在模p意义下的逆元呢 和前面的条件一样p必须是质数 首先求i的逆元时假设我们已经求出[1,i-1]的逆元 我们可以令 rp%i 也就是 p(p/i)*ir 因为p是质数i不等于1时r不等于0 由于等式右边是p所以不难得出 (p/i)*ir0 (mod p) 等式两边同时乘 i-1∗*∗r-1,再移项得: i-1-r-1*(p/i) 因为rir的逆元已知 这样就可以在O1的时间内求出i的逆元 从而做到在On的时间内求出[1,n]的逆元
thanks for reading
真的不点个赞再走吗awa
