逆元的求法（欧拉定理、阶乘逆元、费马小定理、模质数p的情况）

• 乘法逆元

乘法逆元

对于缩系中的元素，每个数a均有唯一的与之对应的乘法逆元x，使得 $math_inline$ax\equiv 1\left(\text{mod}n\right)$math_inline$ ，一个数有逆元的充分必要条件是gcd(a,n)=1，此时逆元唯一存在

在一般数学中，我们所说的逆元就是倒数，但是在数论中，如果一个数字a存在一个对p的逆元x，就可以写成 $math_inline$ax\equiv 1\left(\text{mod}p\right)$math_inline$ 的形式(此处p与a互质，若不互质，则不存在逆元)

逆元的含义：模n意义下，1个数a如果有逆元x，那么除以a相当于乘以x。

满足 $math_inline$a \times k\equiv 1(\text{mod}p)的k值就是a关于p的乘法逆元$math_inline$

当我们要求 $math_inline$\frac{a}{b}\text{mod}p$math_inline$ 的值时，我们就可以用到乘法逆元。我们可以用过求b关于p的乘法逆元k，将a乘上k再模p，即 $math_inline$(a \times k)\text{mod}p$math_inline$ 。其结果与 $math_inline$\frac{a}{b}\text{mod}p$math_inline$ 等价

拓展欧几里得

**拓展欧几里得:** $math_inline$ax+by=\gcd(a,b)$math_inline$ 的解一定存在

当我们要求 $math_inline$a$math_inline$ 关于 $math_inline$p$math_inline$ 的逆元时，若逆元存在，则 $math_inline$\gcd(a,p)=1$math_inline$ 。假设逆元为 $math_inline$x$math_inline$ ，即： $math_inline$ax \equiv 1(\text{mod}p)$math_inline$

我们可以展开一下变成 $math_inline$ax=1+pk$math_inline$ ，由于 $math_inline$k$math_inline$ 可正可负，我们可以得到 $math_inline$ax+pk=1$math_inline$ ，其实就是 $math_inline$ax+by=\gcd(a,b)$math_inline$ 。

我们用拓展欧几里得求出一个最小的x就是 $math_inline$a$math_inline$ 关于 $math_inline$p$math_inline$ 的一个逆元。

求解：

现在我们已经有了 $math_inline$ax+by=\gcd(a,b)$math_inline$ 了。我们想试着求出一个特解 $math_inline$x$math_inline$ 。

根据欧几里得算法我们可以知道 $math_inline$\gcd(a,b)=\gcd(b,a\%b)$math_inline$ 。

而且我们可以看出 $math_inline$bx+(a\%b)y = \gcd(b,\%b)$math_inline$

由此我们可得：(由于两边 $math_inline$x$math_inline$ , $math_inline$y$math_inline$ 值不用，我们用 $math_inline$x'$math_inline$ 和 $math_inline$y'$math_inline$ 进行区分)

我们想要把式子简化一下，可以从 $math_inline$a\%b$math_inline$ 入手，即 $math_inline$a\%b=a-\lfloor \frac{a}{b} \rfloor\times b$math_inline$ 。

所以我们可以化简得到 $math_inline$ax+by=bx'+(a-\lfloor \frac{a}{b} \rfloor\times b)y'$math_inline$

移项： $math_inline$ax+by=ay'+b(x'-\lfloor \frac{a}{b} \rfloor y')$math_inline$

系数相等，所以我们可以解得

根据欧几里得算法，我们一直递归下去，总会到 $math_inline$a\%b=0$math_inline$

所以式子变成了 $math_inline$ax=\gcd(a,b)$math_inline$ 。此时我们取一个特解 $math_inline$x=1,y=0$math_inline$ 。然后往回推，就可以得到一开始的那个x。

此时解出来的 $math_inline$x$math_inline$ 就是 $math_inline$a$math_inline$ 关于 $math_inline$p$math_inline$ 的一个逆元。

PS：算法效率较高，常数较小，时间复杂度 $math_inline$O(\ln{n})$math_inline$

void exgcd(LL a, LL b, LL &x, LL &y) {
	if (b == 0) {
		x = 1;y = 0;
	} else {
		exgcd(b, a%b, y, x);
		y -= (a/b) * x;
	}
}

void extgcd(LL a, LL b, LL &d, LL &x, LL &y) {
    if (!b) {
        d = a;        
        x = 1;
        y = 0;
    } else {
        extgcd(b, a % b, d, y, x);
        y -= x * (a / b);
    }
}

LL inverse(LL a, LL n) {
    LL d, x, y;
    extgcd(a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}

递推求阶乘逆元

我们经常会用到阶乘的逆元，我们可以考虑用费马小定理先求出最大的那个阶乘的逆元，然后再往回推

我们可以把 $math_inline$n!$math_inline$ 的逆元表示为 $math_inline$\left[n!\right]^{-1}$math_inline$ 。

我们要求 $math_inline$(n-1)!$math_inline$ 的逆元，我们可以考虑给 $math_inline$(n-1)!$math_inline$ 乘上一个 $math_inline$n$math_inline$ 把他变为 $math_inline$n!$math_inline$ 。

即 $math_inline$(n-1)!\times n\left[n!\right]^{-1} \equiv 1\text{mod}p$math_inline$

因此 $math_inline$\left[n!\right]^{-1}$math_inline$ 是 $math_inline$(n-1)!$math_inline$ 关于 $math_inline$p$math_inline$ 的一个逆元。

void init() {
	fact[0] = 1;
	for (int i = 1; i < maxn; i++) {
		fact[i] = fact[i - 1] * i %mod;
	}
	inv[maxn - 1] = power(fact[maxn - 1], mod - 2);
	for (int i = maxn - 2; i >= 0; i--) {
		inv[i] = inv[i + 1] * (i + 1) %mod;
	}
}

费马小定理

在模为素数p的情况下，有费马小定理 $math_inline$a^{p-1}\equiv 1(\text{mod}p)$math_inline$ ，（左右同除a）得 $math_inline$a^{p-2}=a^{-1}(\text{mod}p)$math_inline$ ，也就是说a的逆元为 $math_inline$a^{p-2}$math_inline$

而在模数不为素数p得情况下，有欧拉定理 $math_inline$a^{phi(m)}\equiv q (\text{mod}m)\quad(a \perp m)$math_inline$

同理 $math_inline$a^{-1}=a^{phi(m)-1}$math_inline$

因此逆元x便可以套用快速幂求得了 $math_inline$x=a^{phi(m)-1}$math_inline$

如何判断a是否有逆元？检验逆元的性质，看求出的幂值x与a相乘是否为1即可

PS：这种算法复杂度为 $math_inline$O(\log_2(N))$math_inline$ 在几次测试中，常数似乎较上种方法大

当p比较大的时候需要用快速幂求解

LL pow_mod(LL x, LL n, LL mod) {
    LL res = 1;
    while (n > 0) {
        if (n & 1)res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}

当模p不是素数的时候需要用到欧拉定理

所以时间复杂度即求出单个欧拉函数的值

(当p为素数的时候 $math_inline$phi(p)=p-1$math_inline$ ，则 $math_inline$phi(p)-1=p-2$math_inline$ 可以看出欧拉定理是费马小定理的推广)

PS：这里就贴出欧拉定理的板子，很少会用欧拉定理求逆元

特殊情况

一

当N是质数，这点也很好理解。当N是质数， $math_inline$0

CF 696C

二

求逆元一般公式(条件b|a)

证明：

PS：实际上 $math_inline$\frac{a\text{mod}(bm)}{b}$math_inline$ 这种对于所有的都适用，不区分互补互素，而费马小定理和拓展欧几里得算法求逆元是有局限性的，它们都会要求a与m互素，如果a与m不互素，那就没有逆元，这个时候需要 $math_inline$\frac{a\text{mod}(bm)}{b}$math_inline$ 来搞（此时就不是逆元的概念了）。但是当a与m互素的时候，bm可能会很大，不适合套这个一般公式，所以大部分时候还是用逆元来搞

通过递推求1~n的逆元

有时候会遇到这样一种问题，在模质数p下，求 $math_inline$q\sim n$math_inline$ 逆元 $math_inline$n $math_inline$inv[i]=(M-\frac{M}{i}) \times inv[M\%i]\%M$math_inline$

推导过程如下，设 $math_inline$t=\frac{M}{i} \quad k=M\%i$math_inline$

左右同时除 $math_inline$i \times k$math_inline$ ，得到

再把t和k替换掉

初始化 $math_inline$inv[1]=1$math_inline$ ，这样就可以通过递推法求出1->n模奇素数p的所有逆元了

另外有个结论 1->p 模 p的所有逆元值对应 1->p 中所有的数，比如p=7，那么 1->6 对应的逆元是 1 4 5 2 3 6

const int N = 1e5 + 5;
int inv[N];

void inverse(int n, int p) {
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (ll) (p - p / i) * inv[p % i] % p;
    }
}

通过递推求n!的逆元

递推公式： $math_inline$invf[i]=invf[i+1]\times(i+1)\%p$math_inline$

// 快速幂求逆元
int quick_inverse(int n, int p) {
	int ret = 1;
	int exponent = p - 2;
	for (int i = exponent; i; i >>= 1, n = n * n % p) {
		if (i & 1) {
			ret = ret * n % p;
		}
	} 
	return ret;
}
int invf[N], factor[N];
void get_factorial_inverse(int n, int p) {
	factor[0] = 1;
	for (int i = 1; i <= n; ++i) {
		factor[i] = i * factor[i - 1] % p;
	}
	invf[n] = quick_inverse(factor[n], p);
	for (int i = n-1; i >= 0; --i) {
		invf[i] = invf[i + 1] * (i + 1) % p;
	}
}

题目

POJ-1845