noip复习——逆元

逆元，即对给定$a,p\ (a \perp p)$，求$x$使得$ax \equiv 1 \ (\bmod p)$

逆元可以看做$a$在模$p$意义下的$a^{-1}$。因此，在模$p$意义下，可以用乘$a$的逆元的方式来代替除以$a$操作

求单个数的逆元

费马小定理求逆元

当$p$是质数且$a\perp p$时 $$a^{p-1}\equiv1\quad (\bmod p) $$

方程两边同时乘$a^{-1}$,可以发现$$a^{-1}\equiv a ^{p-2}\quad(\bmod p)$$

可以直接快速幂求传送门

欧拉定理求逆元

欧拉定理可以适用于满足$a\perp p$的情况 $$a^{\varphi(p)}\equiv 1\quad (\bmod p) $$

同理可得$$a^{-1}\equiv a^{\varphi(p)-1} \quad (\bmod p) $$

现在的问题变成了，如何求欧拉函数？

1.线性筛$O(p)$求

适用于多个模数的情况传送门

如果是单一模数怎么办呢？有更高效的做法

2.$O(\sqrt{p})$做法

\[\varphi(p)=p\prod\limits_{i}(1-\frac1i)
\]

其中，$i$是$p$的所有质因子

#define LL long long

LL get_phi(LL n)

{

    LL sum = n;

    for (LL i = 1; i * i <= n; ++i)

        if (n % i == 0)

        {

            sum -= sum / i;

            while (n % i == 0)

                n /= i;

        }

    if (n > 1)

        sum -= sum / n;

    return sum;

}

exgcd求逆元

exgcd可以求解方程组$ax+by=c$的解，而求$a$在模$p$下的逆元可以转化为求$ax+py=1$的解

求多个数的逆元

线性求1~n的逆元

题目传送门

令$p=ki+r,k=\lfloor\frac pi \rfloor. r=p \bmod i$

则有$ki+r \equiv 0\quad (\bmod p)$,乘$i^{-1},r^{-1}$可得$kr^{-1}+i^{-1}\equiv 0\quad (\bmod p)$

所以$i^{-1}=-r^{-1}\lfloor\frac pi \rfloor$

显然可以递推求解

线性求n个数的逆元

题目传送门

先预处理出这n个数的前缀积$sum_i$，然后求出这n个数积的逆元$suminv_n$，那么$suminv_{i-1}=suminv_i*a_i$，$inv_i=suminv_{i}*sum_{i-1}$。