数论 · 逆元

· · 个人记录

前言

针对比赛学的一点点逆元，在这里记录一下其中一种方法。

当然求逆元的方法有很多种，之后学到再回来写。 —— 2021.8.24

UPDATE

定义

若 ax \equiv 1\pmod b 且 a\perp b（a，b 互质），

则称 x 为 a 的逆元。

一、费马小定理 + 快速幂

若 p 为质数，且 q \perp p，根据费马小定理，有 q^{p-1} \equiv 1 \pmod {p}，

带入原柿子中就有：

\because ax \equiv 1 \equiv a^{p-1} \pmod p \therefore x \equiv a^{p-2} \pmod p

然后直接用快速幂求解即可。

代码

省略快速幂。

inline int fermat (int a, int n)
{
    return pow_mod (a, n - 2, n);
}

补：费马小定理证明

费马小定理实际上就是 欧拉定理（证明） 的一个特殊情况。

我们定义 \varphi_{x} 为从 1 到 x 和 x 互质的整数的数量。

例如：\varphi_{8}=4，分别是：1、3、5、7。

欧拉定理就是：x^{\varphi_p} \equiv 1 \pmod p。

而费马小定理就是当 p 为质数时的一个特殊情况 。

易证，当 p 为质数时，\varphi_p=p-1。

所以当 p 为质数时，x^{p-1} \equiv 1 \pmod p。

二、扩展欧几里得

\because ax \equiv 1 \pmod p (\text{x 为逆元}) \therefore ax + by=1

这样就可以直接用扩欧求逆元了。

但对于一次性求许多逆元（如洛谷的模板），效率并不高。

数论·扩欧

代码

省略扩欧代码。

inline int exgcd_inv (int a, int n)
{
    int gcd, x, y;
    gcd = exgcd (a, n);//求解方程 ax + ny = gcd (a, n)
    return d == 1 ? (x + n) % n : -1;
}

三、线性求逆元

首先，有 1^{-1} \equiv 1\pmod p，

再设 p=k*i+r,\ r<i,\ 1<i<p，

这样就有 k * i + r \equiv 0 \pmod p，然后给两边同乘上 i 的逆元和 r 的逆元，

可化简得到：k * r^{-1} + i ^{-1} \equiv 0 \pmod p。

易知：k=\left[\dfrac{p}{i}\right] * ,\ r = p \bmod i。

带入上柿可得：

i^{-1} \equiv -\left[\dfrac{p}{i}\right] * (p \bmod i)^{-1} \pmod p

这样就可以用递推求出逆元了。

代码

建数组 inv[]，inv_i 表示 i 的逆元。就有：

inv[i] = -(p / i) * inv[p % i];

用这个方法过了模板题的代码：

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define rint register int
const int maxn = 3e6 + 5;
int inv[maxn], n, q;

signed main ()
{
    scanf ("%lld %lld", &n, &q);
    inv[1] = 1;
    printf ("1\n");
    for (rint i (2); i <= n; ++i)
    {
        inv[i] = ((-(q / i) * inv[q % i]) % q + q) % q;
        printf ("%lld\n", inv[i]);
    }
    return 0;   
}

——End——