逆元

问题引入

对于取余运算，有以下一些性质：

$(a+b)\%p=(a\%p+b\%p)\%p \\ (a-b)\%p=(a\%p-b\%p)\%p \\ (a\times b)\%p=(a\%p\times b\%p)\%p \\ a^b\%p=((a\%p)^b)\%p$

唯独除法是不满足的：

$(\frac{a}{b})\%p \neq (\frac{a\%p}{b\%p})\%p$

证明：

$设a=k_0p+a',b=k_1p+b',k_0,k_1\in Z \\ (\frac{a\%p}{b\%p})=(\frac{a'}{b'})= \frac{(a-k_0p)}{(b-k_1p)} \\ \frac{(a-k_0p)}{(b-k_1p)} \neq \frac{a}{b}$

而对于一些题目，我们必须在中间过程中进行求余，否则数字太大，电脑存不下，那如果这个算式中出现除法，我们就需要逆元了，将除法运算转换为乘法运算。

定义

$若a \cdot c≡1(mod \ b),且a与b互质，就定义c为a的逆元，记作a^{-1}。也可以叫做c为a在mod\ p意义下的倒数。 \\ 所以\frac{a}{b}(mod\ p),就可以求出b(mod\ p)下的逆元，然后乘上a ，再mod\ p,就是这个分数的值了$

除法取余的情况下，就是乘上这个数的逆元。即：

$(\frac{a}{b})\% p=(a\times b^{-1})\% p=((a\% p)\times(b^{-1}\% p))\%p$

这样就把除法取余，装换成了乘法取余。

逆元的性质

唯一性

给定一个数a，若存在模p下的逆元c，c一定唯一。
自反性

c是a的逆元，a也是c的逆元。

逆元的求解

扩展欧几里得算法

$a\cdot a^{-1} ≡ 1(mod\ b)$

模数可以不为质数，满足gcd（a,b)=1即可

定义
$给定两个整数a与b，必存在有整数x与y使得ax+by=gcd(a,b)$

代码模板

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b){
        x=1;y=0;
        return a;
    }
    ll d=exgcd(b,a%b,x,y);
    ll t=x;
    x=y;
    y=t-(a/b)*y;
    return d;
}

即（取非负——a<b）逆元为x：

1	cout<<(x%b+b)%b<<endl;

费马小定理

只适用于模数为质数的情况，如果模数不是质数，可以变换一下，用欧拉定理。

如果p是一个质数（一般为1e9+7），且a不是p的倍数则有：

$a^{p-1}≡1(mod\ p)$

根据同余除法定理，两边同除以a：

$a^{p-2}≡a^{-1}(mod\ p)$

所以：

$a^{-1}=a^{p-2}(mod\ p)$

p是素数,所以a肯定就无法被p整除啊，所以最后就得出a^(p-2)为x的逆元。

代码模板：

ll quickpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)
            res=res*a%p;
        a=a*a%p;
        b>>=1;
    }
    return res;
}

res即为所求逆元。