首页 > 其他分享 >逆元

逆元

时间:2023-08-04 14:44:11浏览次数:27  
标签:费马 inv times 逆元 mod equiv

前言:

依旧,和动态规划一样,逆元这个问题一直困扰了我很久,很烦人。

逆元属于数学问题,要和费马以及欧几里得扯上关系,第一次学习的时候就不是特别懂,造成了很大的问题,遇到有些题目特别是求期望等数学问题最后通常要求 mod 998244353,其实,整数还好,没啥问题,一遇到小数的模运算,就需要用到逆元的知识,这长期影响我连暴力都打不出来的尴尬局面。

逆元定义(Inverse)

就为了打一个逆元符号,刚刚跑去总结了一张常用关系符,哭死

如果 \(ax \equiv 1 (mod\ p)\) 我们就称 \(x\) 为 \(a\) 在模 \(p\) 意义下的乘法的逆

作用和意义是什么?目前唯一作用就是求小数模数的时候把除以一个数改成乘这个数的逆元。至于深层含义,我也没搞太懂。

介绍三种求逆元的方法:

1. 扩展欧几里得算法

简单来说就是逆向欧几里得,

\[ax+yp = 1 \]

然后两边同时除一个 \(p\)

\[as=1 \]

此时 \(s\) 即为 \(a\) 的逆元

2. 费马小定理

费马小定理:若 \(p\) 为质数,则有 \(a^{p-1} \equiv 1 (\mod p)\)

推理: \(a^{p-2} \times a \equiv 1(\mod p)\) ,即 \(a^{p-2}\) 就是 \(a\) 在模 \(p\) 意义下的逆元。

3. 递推法

然后设 \(p=k \times a+r,(r<a)\) 则 \(k\) 是 \(p/a\) 的商,\(r\) 是余数 。

\(k \times a+r≡0(\mod p)\)

\(k \times r^{−1}+a^{−1}≡0(\mod p)\)

\(a^{−1}≡−k∗r^{−1}(\mod p)\)

\(ai^{−1}≡−⌊p/a⌋∗(p\%a)^{−1}(\mod p)\)

代码:

inv[1] = 1;
for(int i = 2; i < p; ++ i)
    inv[i] = (p - p / i) * inv[p % i] % p;

花了我一个上午,代码还没打,溜了,溜了。

标签:费马,inv,times,逆元,mod,equiv
From: https://www.cnblogs.com/alloverzyt/p/17605892.html

相关文章

  • 通过求逆元的几种方式复习基础数论
    逆元若\(ax=1\pmodp\),那么称\(a\)是\(x\)的逆元,显然\(x\)也是\(a\)的逆元。两边同时除以\(a\)得到\(x=\frac1a\pmodp\),可以写成\(x=a^{-1}\pmodp\),这么看来,乘法逆元就是取模意义下的倒数啊。若\(p\)为质数,\(0\)没有逆元,\(1\)的逆元是\(1\),\(p-1\)的逆元......
  • 逆元
     同余:简单来说就是在除法中取模要找到其逆元 逆元:如果一个线性同余方程ax≡1(modb),则x称为amodb的逆元简单来说就是modb是一种环境,而所求的x是a在modb环境中的倒数 以下是求逆元的法子扩展欧几里得法求逆元,时间复杂度o(logn)1voidexgcd(inta,intb,......
  • 乘法逆元
    在数论中,如果a和m是正整数,且它们互质,那么a在模m意义下的逆元是一个正整数x,满足ax≡1(modm)。也就是说,x是一个整数,满足ax除以m的余数为1。求解a模m意义下的逆元有多种方法,其中一种常见的方法是使用快速幂算法。以下是使用快速幂算法求解a模m意义下的逆元的示例代码:int64_tmo......
  • [数学]乘法逆元
    1.定义逆元素,是指一个可以取消另一给定元素运算的元素,在数学里,逆元素广义化了加法中的加法逆元和乘法中的倒数。如果说a在模p意义下的乘法逆元是x,那么ax≡1(modp)2.求逆元的方法·扩展欧几里得同余方程的转化扩展欧几里得的求解代码如下#include<bits/stdc++......
  • O(n)求逆元
    结论\(inv[i]=(mod−mod/i)\timesinv[mod\%i]\%mod\)证明设\(t=mod/i,k=mod\%i\)则有:\(t\timesi+k\equiv0\quad\%mod\)有:\(−t∗i\equivk\quad\%mod\)两边同时除以i∗ki∗k得到:\(−t∗inv[k]\equivinv[i]\quad\%mod\)......
  • 求逆元
    1.线性求\(i\)的逆元for(inti=2;i<=N;++i){inv[i]=(mod-mod/i)*inv[mod%i]%mod;}2.费马小定理求\(i\)的逆元inv[i]=QucikPower(i,mod-2);扩展欧几里得求\(i\)的逆元......
  • 浅谈同余1(常用定理和乘法逆元)
    点个赞吧,球球了~下一篇:$浅谈同余2(扩展欧几里得,中国剩余定理,BSGS)$https://www.acwing.com/file_system/file/content/whole/index/content/7882318/ $\LaTeX$太多了,分成几个部分0x00总写(瞎说)同余是数学中非常重要的东西,这里会写出同余的基本运用若$a\bmodm=b\bmo......
  • 在线 $\Theta(1)$ 逆元
    //createdon23.04.30目录在线O(1)逆元在线O(1)逆元给定质数模数\(p\),多次查询一个数\(a\)的逆元,强制在线。我们有一个\(O(p^{\frac{2}{3}})\)的预处理,\(O(1)\)查询的做法。Farey序列即\(F_n\)表示所有分母不超过\(n\)的最简真分数构成的有序数列(左右端......
  • 初等数论——素数,逆元,EXGCD有关
    初等数论素数定义设整数\(p\ne0,\pm1\)。如果\(p\)除了平凡约数以外没有其他约数,那么称\(p\)为素数(不可约数)。若整数\(a\ne0,\pm1\)且\(a\)不是素数,则称\(a\)为合数。——————OIWiki素数的判定(素性测试)如何判断一个数\(x\)是不是质数?很显然我们可......
  • 在线 $\Theta(1)$ 逆元
    最近看到这个题,想到了一种比较简单的做法。首先,我们考虑给\(x\)乘以一非零整数\(u\),如果我们能求出\(\frac{1}{xu}\),我们就可以通过再乘以\(u\)得到答案。考虑让\(u\)和\(xu\bmodp\)比较接近\(0\),预处理\(|k|\)比较小的所有\(\frac{1}{k}\)。考虑分块:设\(x=......