逆元

Star_LIcsAy · 2021-10-29 18:04:43 · 个人记录

• 同余运算

  • 定义

  整数 a 和整数 b 除以整数 m 的余数相等。记为 a\equiv b(\mod m).

  • 性质

    a(\mod m)+b(\mod m)\equiv a+b(\mod m) a(\mod m)* b(\mod m)\equiv a* b(\mod m)

• 逆元定义

  假设有 a，b，p满足 a* b\equiv 1(\mod p)，则称 b 为 a 在 \mod p 模式下的逆元。

• 费马小定理

  假设 p 为质数，则对于任意整数 a，有：

  a^p\equiv a (\mod p)

  又有：

  a^{p-1}\equiv 1(\mod p)

  则可以得出：

  由此，当 $p$ 可以确定为质数时，可以用 $a^{p-2}$ 来求 $a$ 在 $\mod p$ 模式下的逆元。

• P4942 小凯的数字

  • 此题只需要想清一个问题：

    10\equiv 1(\mod 9)

    由性质 2 可得：

    所以，可以将原式转化为： $$l* 10^{k_1}+(l+1)* 10^{k_2}+(l+2)* 10^{k_3}+...+(r-1)* 10^{k_{n-1}}+r* 10^{k_n}$$ 由上面的式子，又可以转化为： $$l+(l+1)+(l+2)+...+(r-1)+r$$ 最后求这串数字的和 $\mod 9$ 的结果是多少就可以了。

• P3811 【模板】乘法逆元

  • 观察样例可知，所有逆元求出来的结果都小于 p，所以在求出 a^{p-2} 之后可以 \mod p，求得最小逆元。

  • 求 a^{p-2} 时建议使用快速幂，这里提供一种比较简洁的写法：

long long g(int a,int b){//即求a的b次幂
    int x=a;
    long long cnt=1;
    for(;b;b>>=1,x=(x*x)%p)
        if(b&1)
            cnt=(cnt*x)%p;
    return cnt;
}

• 不过这道题只写这个还是过不了，这里就要介绍一个非常高级的东西了：逆元的线性算法。

  假设我们要求的是 i 在 \mod M 意义下的逆元。

  设 t=M/i，k=M\%i，inv[i] 为 i 在 \mod M模式下的逆元，那么就有：

  $-t* i\equiv k(\mod M)$ 即 $(-M+k)\equiv k(\mod M)

  对于上面两个式子同时除以 i* k，我们可以得到：

  -t* inv[k]\equiv inv[i](\mod M)

  再将 t 和 k 置换回去，最终可以得到：

  inv[i]=(M-M/i)* inv[M\%i]\%M

  此时将 inv[1] 初始化为 1，即可继续计算。

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

如果对自己有信心，你可以来试试这个：数论#杂集