乘法逆元

https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
https://en.wikipedia.org/wiki/Fermat's_little_theorem

https://en.wikipedia.org/wiki/Euler's_totient_function
https://en.wikipedia.org/wiki/Euler's_theorem

逆元

数学中，逆元素（英语：Inverse element）推广了加法中的加法逆元和乘法中的倒数。直观地说，它是一个可以取消另一给定元素运算的元素。

加法逆元

对于一个任意数n，存在加法逆元（英语：Additive Inverse，又称相反数），其与$n$的和为零（加法单位元）。$n$的加法逆元表示为$-n$。

乘法逆元

数学上，一个数$x$的倒数（reciprocal），或称乘法逆元（multiplicative inverse），是指一个与$x$相乘的积为$1$的数。显然在实数范围内$x$的乘法逆元是$\frac{1}{x}$。

信息学中常用的乘法逆元是模逆元。
一整数a对同余n之模逆元是指满足以下公式的整数$b$
$$a b \equiv 1 \pmod {n}.$$
整数$a$对模数$n$之模逆元存在的充分必要条件是$a$和$n$互素，若此模逆元存在，在模数$n$ 下的除法可以用和对应模逆元的乘法来达成，此概念和实数除法的概念相同。

如何求单个数字乘法逆元

暴力求逆元

$$a b \equiv 1 \pmod {n}.$$
希望求$a$的逆元，可以暴力枚举$b$从$1$到$n-1$。

另一种暴力方法是
希望解出$ax + py = 1$的一组解，$|x| < p, |y| < a$
枚举$y$计算对于哪个$y$满足$x = (1 + py) / a$是整数

质数

快速幂

对于质数$p$，考虑费马小定理$a^{p-1} \bmod p = 1$，就说明 $a \times a^{p-2} \bmod p = 1$ 可以得到$a$的逆元是pow(a, p - 2, p)。

https://en.wikipedia.org/wiki/Fermat's_little_theorem

使用$O(n)$求乘法逆元的递归版

$O(n)$求乘法逆元的公式可以改写为递归版，以替代质数情况下用快速幂求逆元。

int inv(int x) {
    if (x == 1) {
        return 1;
    } else {
        return (long long)inv(p % i) * (p - p / i) % p;
    }
}

时间复杂度未知，大约是$O(\sqrt{n})$到$O(\log n)$
https://www.zhihu.com/question/59033693

合数

扩展欧几里得

因为快速幂非常好写，一般只有在模合数，或者是卡常数的情况下使用这个算法。
解出$ax + py = 1$的一组解$(x, y)$，那么 $ax \bmod p = 1$，$x$就是$a$关于模$p$的其中一个模逆元。
需要注意求解出的$x$可能是负数，需要通过加$p$。

欧拉定理

对于合数$p$，考虑欧拉定理$a^{\varphi(p)} \bmod p = 1$，就说明 $a \times a^{\varphi(p) - 1} \bmod p = 1$ 可以得到$i$的逆元是pow(i, phi(p) - 1, p)。
但是因为对于一般的数字计算$\varphi(p)$复杂度较高，并不使用这个方法。

$O(n)$求$1$到$n$模质数的乘法逆元

直接用公式

把 $p$ 表示为 商乘以除数加余数
$$(\lfloor p / i \rfloor \times i) + (p \bmod i) = 0\pmod p$$

把 $i$ 和 $p \bmod i$ 分开
$$(p \bmod i) = - \lfloor p / i \rfloor \times i \pmod p$$

把 $i$ 和 $p \bmod i$ 转化成逆元
$$i^{-1} \times (p \bmod i) = - \lfloor p / i \rfloor \pmod p$$

$$i^{-1} = - \lfloor p / i \rfloor \times (p \bmod i)^{-1} \pmod p$$

避免负数，加$p$。
$$i^{-1} = (p - \lfloor p / i \rfloor) \times (p \bmod i)^{-1} \pmod p$$

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

这个方法可以用于组合数的预处理。

阶乘求逆元

另一个常用与组合数预处理的做法是：
先预处理出$1!$到$n!$，然后计算$n!$的逆元，然后倒序推出$(n-1)!$到$1!$的逆元。

fac[0] = 1;
for (int i = 1; i <= n; i++) {
    fac[i] = (long long)fac[i - 1] * i % p;
}
invfac[n] = pow(fac[n], p - 2, p);
for (int i = n - 1; i >= 0; i--) {
    invfac[i] = (long long)invfac[i + 1] * (i + 1) % p;
}

利用积性函数

乘法逆元是完全积性函数，只需要对质数求逆元即可，这种写法已经被淘汰了，如果$1$到$n$模合数的乘法逆元

完全积性函数

对于任意$x,y$ $f(xy) = f(x)f(y)$
$$f(x) = x^k$$
$k$可以是$0$或者$-1$

完全积性函数只需要确定质数的值，就可以确定所有数字的值，结合筛法使用

$$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$

$$f(n) = f(p_1)^{a_1}f(p_2)^{a_2} \cdots f(p_k)^{a_k}$$

积性函数

对于互质的$x,y$ $f(xy) = f(x)f(y)$
例子：欧拉函数，莫比乌斯函数，约数个数函数，约数和函数

积性函数只需要确定质数次幂的值，就可以确定所有数字的值，结合筛法使用

$$n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$$

$$f(n) = f(p_1^{a_1})f(p_2^{a_2}) \cdots f(p_k^{a_k})$$

Python求乘法逆元

可以直接使用 pow(a, -1, p) 求出 a 的乘法逆元，即使 p 不是质数，只需要保证 a 和 p 互质即可

线性求任意 n 个数的逆元

https://www.luogu.com.cn/problem/P5431

参考题目

P1082 [NOIP2012 提高组] 同余方程

https://www.luogu.com.cn/problem/P1082

题目描述

求关于$x$的同余方程 $a x \equiv 1 \pmod {b}$ 的最小正整数解。

输入格式

一行，包含两个正整数 $a,b$，用一个空格隔开。

输出格式

一个正整数 $x_0$，即最小正整数解。输入数据保证一定有解。

样例 #1

样例输入 #1

3 10

样例输出 #1

7

提示

【数据范围】

对于 40%的数据，$2 ≤b≤ 1,000$；

对于 60%的数据，$2 ≤b≤ 50,000,000$；

对于 100%的数据，$2 ≤a, b≤ 2,000,000,000$。

NOIP 2012 提高组 第二天 第一题

参考代码

#include <bits/stdc++.h>
using namespace std;
void exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return;
	} else {
		exgcd(b, a % b, y, x);
		y -= a / b * x;
	}
}
int main() {
	int a, b, x, y;
	cin >> a >> b;
	exgcd(a, b, x, y);
	if (x < 0) {
		x += b;
		y -= a;
	}
	cout << x << endl;
}

题解

乘法逆元
直接扩展欧几里得

模合数
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
扩展欧几里得
a * x + b * y = gcd(a, b)
|x| + |y| 越小越好

输入 a 和 b，保证 a 和 b 互质
求a x % b == 1
a x + b y == 1

需要注意最终求出的 x 可能是负数

P3811 【模板】乘法逆元

https://www.luogu.com.cn/problem/P3811

题目背景

这是一道模板题

题目描述

给定 $n,p$ 求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。

这里 $a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。

输入格式

一行两个正整数 $n,p$。

输出格式

输出 $n$ 行，第 $i$ 行表示 $i$ 在模 $p$ 下的乘法逆元。

样例 #1

样例输入 #1

10 13

样例输出 #1

1
7
9
10
8
11
2
5
3
4

提示

$1 \leq n \leq 3 \times 10 ^ 6, n < p < 20000528$

输入保证 $p$ 为质数。

参考代码

#include <bits/stdc++.h>
using namespace std;
int v[3000020];
int n, p;
int main() {
	scanf("%d%d", &n, &p);
	v[1] = 1;
	printf("%d\n", 1);
	for (int i = 2; i <= n; i++) {
		v[i] = (long long)v[p % i] * (p - p / i) % p;
		printf("%d\n", v[i]);
	}
}

题解

$O(n)$ 预处理$1$到$n$的乘法逆元

1. v[i] = (long long)v[p % i] * (p - p / i) % p;
2. 求n!的逆元，倒序推出 (n-1)! (n-2)! ... 2! 1!
3. 注意到逆元是完全积性函数，暴力计算所有质数的逆元，合数的逆元分解为两部分乘起来

P2613 【模板】有理数取余

https://www.luogu.com.cn/problem/P2613

题目描述

给出一个有理数 $c=\frac{a}{b}$，求 $c \bmod 19260817$ 的值。

这个值被定义为 $bx\equiv a\pmod{19260817}$ 的解。

输入格式

一共两行。

第一行，一个整数 $a$。
第二行，一个整数 $b$。

输出格式

一个整数，代表求余后的结果。如果无解，输出 Angry!。

样例 #1

样例输入 #1

233
666

样例输出 #1

18595654

提示

对于所有数据，保证 $0\leq a \leq 10^{10001}$，$1 \leq b \leq 10^{10001}$，且 $a, b$ 不同时是 $19260817$ 的倍数。

参考代码

#include <bits/stdc++.h>
using namespace std;
char s[10020];
int a[10020];
int p = 19260817;
int read() {
	// 读入一个数字mod p的结果 
	scanf("%s", s);
	int n = strlen(s);
	for (int i = 0; i < n; i++) {
		a[i] = s[n - i - 1] - '0';
	}
	int u = 0;
	for (int i = n - 1; i >= 0; i--) {
		u = u * 10 + a[i];
		u %= p;
	}
	return u;
}
long long pw(long long x, long long y, long long p) {
	long long re = 1;
	for (; y; y >>= 1) {
		if (y & 1) {
			re = re * x % p;
		}
		x = x * x % p;
	}
	return re;
}
int main() {
	int A = read();
	int B = read();
	if (B == 0) {
		printf("Angry!");
	} else {
		cout << (A * pw(B, p - 2, p) % p) << endl;
	}
}

题解

直接扩展欧几里得

参考资料

贾志鹏线性筛