逆元运算（除法取模） |
您所在的位置：网站首页 › 逆运算公式加减 › 逆元运算（除法取模） |
逆元运算（除法取模）
|
一、简介
逆元：ax≡1（mod p）当a和p互质时，方程的解 x 称为a关于p的逆元， 在普通的四则运算中，只有加减乘三种运算可以根进行分别取余运算，因为这三种运算都是从低位到高位的运算，而对于除法是从高位到低位的运算，显然不能直接进行取余，这时候，就要用到逆元有关的运算。 逆元可以近似的看作倒数的概念 二、应用 例如， 如果要求（x / y）%p ，显然不可以（x%p）/（y%p）， 利用逆元运算：可以将（x / y）%p化为 （x * Y ）%p ，其中Y是y关于p的逆元
那么怎么求Y呢： 由逆元的定义，有yY≡1（mod p）， 费马小定理：如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡ 1（mod p）。 我们分离一项出来 a • a^(p-2) ≡ 1（mod p）. 对比逆元的方程式，可以很容易得到，a关于p的逆元就是 a^(p-2)，那么Y==y^(p-2)。
证明转化过程： 费马小定理： y • y^(p-2) % p ==1 两边乘以x/y： x • y^(p-2) % p == x / y
注意以上所有的的运算和推导过程都要在一个前提条件下： x和p互质，即gcd（x，p）==1
三、实现 有了以上理论基础，就可以很容易实现了 1、快速幂取模版 #include #define lom long long using namespace std; lom quick(lom a,lom b,lom c)//快速幂取模 { lom ans=1; a%=c; while(b) { if(b&1) ans=ans*a%c; a=a*a%c; b>>=1; } return ans%c; } lom divi(lom a,lom b,lom p) { b=quick(b,p-2,p); //b的逆元 return a*b%p; }2、递推版 证明： 们要求i在模p意义下的逆元inv[i]，那么我们就设ki+r=p，所以ki+r ≡ 0(mod p)。 移项可以得到：r ≡ -ki (mod p)。 两边同时除以ir，就可以得到这个式子：
那么i分之一就是i在模p意义下的逆元，r分之一就是r在模p意义下的逆元。 变成这个式子：inv[i] ≡ -k*inv[r](mod p)。 因为r |
【本文地址】
今日新闻 |
推荐新闻 |