质数与约数

质数

定义

质数与合数的定义：质数与合数是针对所有大于 11 的自然数来定义的，也就是说所有小于等于 11 的数字都不属于质数和合数的范围。 在大于 11 的整数中，如果只包含 11 和本身两个约数，就被称为质数（素数）；反之为合数。

线性判断质数

很容易可以想到，只需要枚举 2∼n−12 \sim n-1 的所有数字，依次判断它们能否整除 nn，只要有一个可以就是合数；而如果都不能整除，则是质数，由此可以得到代码：

bool is_prime(int n) {
	if (n < 2) return 0;
	for (int i=2; i<=n-1; i++) {
		if (n%i == 0) return 0;
	}
	return 1;
}

容易发现，上面这个代码的时间复杂度是 O(n)O(n) 级别的，那么在面对 nn 较大或者判断次数比较多时，会有超时的风险。

n\sqrt n 判断质数

在学习这个方法前，我们需要知道一个性质：如果 ii 可以整除 nn，那么 n/in/i 必然也可以整除 nn 。 所以根据这个性质，我们只需要枚举完所有较小的数字即可，可以列出如下公式：

$$i \leq n/i \rightarrow i \times i \leq n \rightarrow i \leq \sqrt n$$

所以上面代码可以优化为：

bool is_prime(int n) {
	if (n < 2) return 0;
	for (int i=2; i<=n/i; i++) {  // 写 i<=sqrt(n)也可以，但是还需要算，比较慢。
		if (n%i == 0) return 0;
	}
	return 1;
}

这样代码的时间复杂度就变成了 O(n)O(\sqrt n) 。

分解质因数

分解质因数应该是很多同学都熟悉的数学题，要把一个合数分解成多个质数相乘的结果。容易想到一个解法，枚举所有可能的质数，然后让这个质数一直去除 nn，直到不能整除为止。

这样做确实可以，但其实我们没有必要去枚举质数，直接枚举 2∼n−12 \sim n-1 然后一直除就可以了，不用管这个数字是否是质数，为什么呢？可以思考一下。

[!NOTE] 证明过程 假设当前枚举的数 ii 是合数，那么前面必然已经枚举过 ii 的质因子了，所以在前面已经通过不断的除使得质因子无法整除 nn 了，既然质因子都无法整除，作为合数的 ii 必然也不可能整除，所以合数 ii 并不会影响程序的结果，也就不需要去判断质数合数。

那么可以得到如下代码：

void divide(int n) {
	// 对数字 n 进行分解质因数
	for (int i=2; i<=n-1; i++) {
		if (n%i == 0) {
			int cnt = 0;
			while (n%i == 0) {
				n /= i;
				cnt++;
			}
			printf("%d %d\n", i, cnt);
		}
	}
}

同样的，这个代码也是 O(n)O(n) 级别的时间复杂度，能否让算法更快一点呢？很容易能想到，大于 n/in/i 的质因子最多只会有 11 个，否则如果有两个的话，它俩乘起来就比 nn 大了，这肯定不可能。

所以，我们枚举的范围同样可以只到 n/in/i，而如果最后计算完后 n!=1n != 1 的话，那现在它里面的数字一定就是那个最后的质因子，代码成功优化为了 O(n)O(\sqrt n) 的时间复杂度(最好情况是 O(logn)O(log n))。

void divide(int n) {
	// 对数字 n 进行分解质因数
	for (int i=2; i<=n/i; i++) {
		if (n%i == 0) {
			int cnt = 0;
			while (n%i == 0) {
				n /= i;
				cnt++;
			}
			printf("%d %d\n", i, cnt);
		}
	}
	if (n > 1) printf("%d %d\n", n, 1);
}

质数筛

在需要多次判断质数的场景，比如统计某个区间内的所有质数时，O(n)O(\sqrt n) 的速度还是太慢了，能否更快呢？这时候就要用到质数筛法了，常见的筛法有 朴素筛、埃氏筛和欧拉筛。

朴素筛

筛法的思想很简单，数字的倍数一定不是质数。那么在选到一个数字时，把这个数字的所有倍数全部筛掉，这样过一轮之后，所有的质数也就被筛选出来了。 如果要用STL实现，就把 primes 数组替换为 vector<int>

const int N = 1e6+5;
int primes[N], cnt;  // primes用来存储质数，cnt是对应数组的下标
bool st[N];  // st[i]标记数字是否被筛掉

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
			if (!st[i]) {
				primes[++cnt] = i;  // 质数存到数组中
		}
		for (int j=i+i; j<=n; j+=i) st[j] = 1;  // 筛掉数字的倍数
	}
	// 这样过完之后，所有的质数就存到了primes数组中
	// 同时 st 中标记了每个数字是否是质数。
}

这段代码的时间复杂度约为 O(nlog⁡en)O(n \log_e n) ，略快于 O(nlog⁡2n)O(n \log_2 n)，空间复杂度为 O(n)O(n) 。

埃氏筛

可以发现，其实没必要把所有的数字的倍数都遍历一遍，因为如果数字是一个合数，它的倍数肯定也被之前的质数筛掉了，所以只需要遍历质数的倍数；这也是筛法的核心思想：质数的倍数一定不是质数。

const int N = 1e6+5;
int primes[N], cnt;  // primes用来存储质数，cnt是对应数组的下标
bool st[N];  // st[i]标记数字是否被筛掉

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) {
			primes[++cnt] = i;  // 质数存到数组中
			for (int j=i+i; j<=n; j+=i) st[j] = 1;  // 筛掉质数的倍数
		}
	}
	// 这样过完之后，所有的质数就存到了primes数组中
	// 同时 st 中标记了每个数字是否是质数。
}

这段代码的时间复杂度约为 O(nlog⁡2(log⁡2n))O(n \log_2 ({\log_2 n})) ，空间复杂度为 O(n)O(n) 。

欧拉筛(线性筛)

在埃氏筛中，为什么代码会耗时呢，是因为在遍历质数的倍数时，会重复标记很多数字，例如数字 1212，既是 22 的倍数，也是 33 的倍数，那不管我们是扫描 22 还是扫描 33，一定都会把 1212 去重复筛掉。 有什么办法可以让每个数字都只被筛一次呢？先来看下面这段代码：

void get_primes(int n) {
	// 筛选 2~n中的所有质数
	for (int i=2; i<=n; i++) {
		if (!st[i]) primes[++cnt] = i;  // 质数存到数组中
			// primes[j] <= n/i 理解为 primes[j]*i <= n，即只筛n范围内的数字
			for (int j=1; primes[j]<=n/i; j++) {
				st[primes[j]*i] = 1;  // 筛掉i的素数倍数
				if (i%primes[j] == 0) break;  // 线性复杂度的关键
			}
	}
}

这段代码乍一看很莫名其妙，感觉既不能筛掉所有的合数，也没法保证 O(n)O(n) 的时间复杂度，但是数学就是如此的神奇，让我们往下看。

这个算法称为欧拉筛法，其核心思想是每个合数都可以分解为一个最小质因数乘以另一个数的形式，即 合数 = 最小质因数 * 自然数，在上述代码中，st[primes[j]*i] = 1 做的工作就是把以 primes[j] 为最小质因数的数字给筛掉，来看一段表格：

i primes 筛掉的数字
2 4
3 2,3 6,9
4 8
5 2,3,5 10,15,25
6 12
7 2,3,5,7 14,21,35,49
8 16
9 18,27
10 20
首先可以发现，每个数字都是被自己的最小质因子筛掉的，比如 44 是被 22 筛掉的，1212 是被 22 筛掉的，如何证明这一点呢？

[!INFO] 被最小质因子筛 证明 这还要基于 if (i%primes[j]==0) break; 这段代码来证明，根据这个条件，我们代码中会有两种情况：

情况一：i % primes[j] == 0，那么 primes[j] 一定是 i 的最小质因子，否则肯定已经 break 了；因此 primes[j]*i 的最小质因子也必然是 primes[j] 。

情况二：i % primes[j] != 0 ，那么 primes[j] 一定小于 i 的最小质因子，否则在前面肯定已经 break 了；因此 primes[j]*i 的最小质因子必然是 primes[j] 。

因为每个数字都会被最小质因子筛掉，所以每个数字实际都只会被标记依次，那么时间复杂度就接近 O(n)O(n) 了。 可能同学们还会有一个疑问，就是这样写代码不会漏掉一些数字么？当然不会，请看下面：

[!INFO] 欧拉筛正确性证明

假设现在要筛掉 合数 aa，并且 aa 的最小质因数为 bb，令 a=p1×ba = p_1 \times b；在遇到 aa 的时候，bb 必然已经在 primes 数组中了，而 p1p_1 这个数字显然一定在 b∼ab \sim a 这个范围内，所以在遇到 aa 之前，aa 这个数字肯定已经被筛掉了。

以上便是关于欧拉筛的模板与证明，欧拉筛的时间复杂度为 O(n)O(n)，当 nn 达到 1e71e7 时，埃氏筛与欧拉筛的性能差一倍左右。在一般情况下，进行质数筛时我们都可以选用欧拉筛法，而埃氏筛的思想也是很重要的。

约数

定义

约数的概念很简单，如果 aa 能够整除 bb，那么 aa 是 bb 的约数，bb 是 aa 的倍数。

线性枚举约数

容易想到，枚举 1∼n1 \sim n 的数字，然后依次判断并加到数组中即可，代码如下所示：

const int N = 1e5+5;
int res[N], cnt;

void get_divisors(int n) {
	for (int i=1; i<=n; i++) {
		if (n%i == 0) res[++cnt] = i;
	}
}

显然，这样做的时间复杂度是 O(n)O(n) 级别的，能否更快呢？

n\sqrt n 枚举约数

还是质数时讲过的性质：如果 ii 可以整除 nn，那么 n/in/i 必然也可以整除 nn 。所以我们枚举的时候，可以只枚举到 n/in/i，然后当 ii 可以整除 nn 时，把 ii 和 n/in/i 都加入到数组中即可，这样代码的时间复杂度就到了 O(n)O(\sqrt n)

const int N = 1e5+5;
int res[N], cnt;

void get_divisors(int n) {
	for (int i=1; i<=n/i; i++) {
		if (n%i == 0) {
			res[++cnt] = i;
			if (i != n/i) res[++cnt] = n/i;  // 这个判断是防止加两次 n/i 进去
		}
	}
	sort(res+1, res+1+cnt);  // 如果不要求排序，也可以不用。
	// 另外，也可以用两个数组，一个存前半部分一个存后半部分，最后合并，比排序更快。
}

例题-约数个数

一个数的约数个数可以通过其质因数分解来确定。具体来说，如果一个数 nn 可以被分解为质因数的乘积，即 $n = p_1^{x_1} \times p_2^{x_2} \times \cdots \times p_k^{x_k}$，那么 nn 的约数个数 rr 可以通过以下公式计算：

$$r = (x_1 + 1) \times (x_2 + 1) \times \cdots \times (x_k + 1)$$

例如，数字 378000378000 可以被分解为 24×33×53×712^4 \times 3^3 \times 5^3 \times 7^1)，因此它的约数个数为：

$$(4 + 1) \times (3 + 1) \times (3 + 1) \times (1 + 1) = 160$$

[!NOTE] 定理简证 容易发现，p1x1p_1^{x_1} 的约数有：p10,p11,p12⋯p1x1p_1^0,p_1^1,p_1^2 \cdots p_1^{x_1}，共 x1+1x_1+1 个；同理可得 p2x2p_2^{x_2} 的约数有 x2+1x_2+1 个；一直到 pkxkp_k^{x_k} 的约数有 xk+1x_k+1 个，根据乘法原理可知，nn 的约数个数就是 (x1+1)×(x2+2)×...×(xk+1)(x_1+1) \times (x_2+2) \times ... \times (x_k+1)。

来看例题：

题目描述

给定 nn 个正整数 aia_i，请你输出这些数的乘积的约数个数，答案对 109+710^9+7 取模。

输入格式

第一行包含整数 nn。 接下来 nn 行，每行包含一个整数 aia_i。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 109+710^9+7 取模。

样例输入

3
2
6
8

样例输出

12

题目分析

根据上述公式可得，我们只需要对每个 aia_i 进行质因数分解，统计所有质因子的指数，然后求和即可，因为数字范围比较大，所以可以使用 unordered_map 来记录每个质因子的出现次数。

示例代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

unordered_map<int, int> mp;

void get_cnt(int n) {
	for (int i=2; i<=n/i; i++) {  // 分解质因数
		while (n%i == 0) {
			n /= i;
			mp[i]++;  // 统计这个质因数的指数
		}
	}
	if (n > 1) mp[n]++;  // 单独处理比 n/i 大的质因子
}

int main() {
	int n, x;
	long long res = 1;
	cin >> n;
	for (int i=1; i<=n; i++) {
		cin >> x;
		get_cnt(x);
	}
	for (auto i:mp) res = res*(i.second+1) % MOD;  // 计算结果
	cout << res;
	return 0;
}

约数之和

题目描述

给定 nn 个正整数 aia_i，请你输出这些数的乘积的约数之和，答案对 109+710^9+7 取模。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个整数 aia_i。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 109+710^9+7 取模。

样例输入

3
2
6
8

样例输出

252

题目分析

还是基于分解质因数的公式来计算。如果 $n = p_1^{x_1} \times p_2^{x_2} \times \cdots \times p_k^{x_k}$，那么来显然 p1x1p_1^{x_1} 的约数有 p10,p11,⋯ ,p1x1p_1^0,p_1^1, \cdots , p_1^{x_1}，同理可得，pkxkp_k^{x_k} 的约数有 pk0,pk1,⋯pkxkp_k^0,p_k^1, \cdots p_k^{x_k}。

我们来用实际的数字进行推导，88 分解质因数后是 232^3 ，它的约数有 20,21,22,232^0,2^1,2^2,2^3， 那显然可得它的约数之和是 20+21+22+232^0+2^1+2^2+2^3 。 那 7272 分解质因数后是 23×322^3 \times 3^2，它的约数除了上述 88 的约数之外，还会有 $2^0 \times 3^1, 2^1 \times 3^1, 2^2 \times 3^1, 2^3 \times 3^1, 2^0 \times 3^2, 2^1 \times 3^2, 2^2 \times 3^2, 2^3 \times 3^2$。

假设 m=20+21+22+23m = 2^0+2^1+2^2+2^3，那么可得 7272 的因数之和为：

$$2^0+2^1+2^2+2^3+2^0 \times 3^1+2^1 \times 3^1+2^2 \times 3^1+2^3 \times 3^1+2^0 \times 3^2+2^1 \times 3^2+2^2 \times 3^2+2^3 \times 3^2$$

即：

$$m + m \times 3^1 + m \times 3^2 \rightarrow m \times (3^0+3^1+3^2) \rightarrow (2^0+2^1+2^2+2^3) \times (3^0+3^1+3^2)$$

聪明的你再往下推一步，如果是 360360 分解质因数，得到的是 23×32×512^3 \times 3^2 \times 5^1，那么它的因数之和是多少呢？

揭晓答案，应该是：

$$(2^0+2^1+2^2+2^3) \times (3^0+3^1+3^2) \times (5^0+5^1)$$

所以，根据数学归纳法可得，当 $n = p_1^{x_1} \times p_2^{x_2} \times \cdots \times p_k^{x_k}$ 时，其约数和为：

$$s = (p_1^0+p_1^1+ \cdots + p_1^{x_1}) \times (p_2^0+p_2^1+ \cdots + p_2^{x_2}) \times \cdots \times (p_k^0+p_k^1+ \cdots + p_k^{x_k})$$

根据上面的公式，来求出这个代码吧！

[!INFO] 提示 如何计算 p0+p1+⋯+pnp^0+p^1+ \cdots +p^n 呢？

1×n+1=n+11 \times n + 1 = n+1

(1×n+1)×n+1=n2+n+1(1 \times n+1) \times n+1 = n^2+n+1

...

示例代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
unordered_map<int, int> mp;

void get_cnt(int n) {
	// 此处实现同上段代码，不再演示
}

int main() {
	int n, x;
	long long res = 1;
	
	cin >> n;
	for (int i=1; i<=n; i++) {  // 求出所有质因子的指数
		cin >> x;
		get_cnt(x);
	}

	for (auto i:mp) {
		long long sum=1, a=i.first, b=i.second;
		while (b--) {  // 求解的关键，写法很多，也可以再来个变量，一项一项算然后求和。
			sum = (sum*a+1) % MOD;
		}
		res = res*sum % MOD;  // 一定要记得边算边模，否则数据会溢出
	}
	cout << res;
    return 0;
}

最大公约数

定义

最大公约数(GCD)，指两个或多个整数共有的约数中最大的一个，例如 1212 和 1616 的公约数由 1,2,41,2,4，其中最大的一个是 44，所以 44 是 1212 和 1616 的最大公约数，aa 和 bb 的最大公约数记为 gcd(a,b)gcd(a,b)，最大公约数在数论问题中是特别重要的概念。

线性找最大公约数

很容易想到，如果要求 aa 和 bb 的最大公约数，我们只需要把 min(a,b)∼1min(a,b) \sim 1 的数字列出来，然后找到第一个能同时整除 aa 和 bb 的数字，就是最大公约数了，代码如下：

int gcd(int a, int b) {
	// 为什么是 min(a,b) 呢？因为约数的范围不会超过这个数字。
	for (int i=min(a,b); i>=1; i--) {
		if (a%i==0 and b%i==0) return i;
	}
}

显然，这个代码的时间复杂度是 O(n)O(n) 级别的。

辗转相除法

欧几里得算法又称辗转相除法，原理为 $gcd(a,\; b) = gcd(b,\; a\%b), (a >= b,\; a\%b != 0)$。

[!INFO] 证明过程 令 a=k×b+ra = k \times b + r，即 r=a%br = a \% b（a,b,k,ra,b,k,r 均为正整数）。

设 dd 为 a,ba,b 的任意一个公约数，而根据上式可得 r=a−k×br = a-k \times b，两边同时除以 dd，可得 r/d=a/d−k×b/dr/d = a/d - k \times b / d。

因为 a/d−k×b/da/d - k \times b/d 必然是一个整数，所以 r/dr/d 也是整数，也就意味着 dd 也是 rr 的约数，又因 r=a%br = a \% b，所以 a,ba,b 和 b,a%bb,a\%b 的公约数是一样的，所以最大公约数必然也一样，得证 gcd(a,  b)=gcd(b,  a%b)gcd(a, \;b) = gcd(b, \;a\%b) 。

辗转相除法便是利用这个原理不断往下计算，直到 a%ba\% b 为 00 时，时间复杂度约为 O(log⁡n)O(\log n)，尝试自己实现下这个代码吧！

示例代码

int gcd(int a, int b) {
	// 可以简写为 return b ? gcd(b, a%b) : a;
	if (a%b == 0) return b;
	else return gcd(b, a%b);
}

快速幂

什么是幂

幂是一个数自乘若干次的形式，乘方的结果叫做幂。比如 nn 的 mm 次幂意为 mm 个 nn 相乘，写作 nmn ^ m，其中 nn 称为底数，mm 称为指数。

[!INFO] 幂运算的性质 这些性质都是针对任意实数 a,ba,b 以及自然数 n,mn, m 所得的结论。

同底数幂的乘法法则 an×am=an+ma^{n} \times a^{m}=a^{n+m}

同底数幂的除法法则 an/am=an−ma^{n} / a^{m}=a^{n-m}

幂的幂 (an)m=an×m(a^{n})^{m}=a^{n \times m}

积的幂 (a×b)n=an×bn(a \times b)^{n}=a^{n}\times b^n

商的幂 (a/b)n=an/bn(a/b)^{n}=a^{n}/b^{n}

线性求幂

容易想到，求 ana^n 只需要循环 nn 次，每次乘 aa 即可，时间复杂度是 O(n)O(n)，代码如下：

int sum=1;
for (int i=1; i<=n; i++) sum *= a;

那能否更快呢？

快速幂

来看例题：

例题——快速幂

题目描述

给定 nn 组 ai,bi,piai,bi,pi，对于每组数据，求出 aibi  mod  pia_i^{b_i} \;mod\; p_i 的值。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含三个整数 ai,bi,piai,bi,pi。

输出格式

对于每组数据，输出一个结果，表示 aibi  mod  pia_i^{b_i} \;mod\; p_i 的值。

每个结果占一行。

样例输入

2
3 2 5
4 3 9

样例输出

4
1

题目分析

首先我们需要知道幂运算的性质，am×an=am+na^m \times a^n = a^{m+n}，又因在位运算章节中，我们学习过数字转二进制，必然可以把数字 kk 转为 2x0+2x1+⋯+2xi2^{x_0}+2^{x_1}+ \cdots + 2^{x_i} 的形式，综合起来可得：

ak=a(2x0+2x1+⋯+2xi)a^k = a^{(2^{x_0}+2^{x_1}+ \cdots + 2^{x_i})}

举个例子：

520=522+245^{20} = 5^{2^2+2^4}

这样表示有什么好处呢，请看下面的式子：

$$\begin{align} 5^{2^1} &= 5^{2^0} \times 5^{2^0} \\ 5^{2^2} &= 5^{2^1} \times 5^{2^1} \\ &\cdots \\ 5^{2^{x_i}} &= 5^{2^{x_{i-1}}} \times 5^{2^{x_{i-1}}} \end{align}$$

易得：

a2k=a2k−1×a2k−1a^{2^k} = a^{2^{k-1}} \times a^{2^{k-1}}

这意味着什么呢？如果我们把 aka^k 拆解成 a(2x0+2x1+⋯+2xi)a^{(2^{x_0}+2^{x_1}+ \cdots + 2^{x_i})} 的形式，那么我们就可以利用上面的公式，从 a20a^{2^0} 开始，一路往上递推，直到 a2xia^{2^{x_i}}，并在这个过程中把所有要的数字都乘起来求出结果。 而把 kk 拆成二进制的时间复杂度为 O(log⁡k)O(\log k)，所以只需要这个复杂度就可以求出 aka^k 。

示例代码

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

long long qmi(int a, int k, int p) {
	long long res = 1;
	while (k) {
		if (k&1) res = res*a % p;  // 如果二进制上这位有数字，那么结果乘起来
		k >>= 1;  // 去掉最低位
		a = (long long)a*a % p;  // 递推求出 a^(2^x) 的值
	}
	return res;
}

int main() {
	int a, k, p;
	cin >> a >> k >> p;
	cin >> a >> k >> p;
	cout << qmi(a, k, p) << '\n';
	return 0;
}

例题——快速幂求逆元

题目描述

给定 nn 组 ai,pia_i,p_i，其中 pip_i 是质数，求 aia_i 模 pip_i 的乘法逆元，若逆元不存在则输出 impossible。

注意：请返回在 0∼p−10∼p−1 之间的逆元。

[!INFO] 乘法逆元的定义

若整数 b,mb, m 互质，并且对于任意的整数 aa，如果满足 b∣ab|a，则存在一个整数 xx，使得 ab≡a×x  (mod  m)\frac{a}{b}≡a×x\;(mod\;m)，则称 xx 为 bb 的模 mm 乘法逆元，记为 b−1  (mod  m)b−1\;(mod\;m)。

bb 存在乘法逆元的充要条件是 bb 与模数 mm 互质。当模数 mm 为质数时，bm−2b^{m−2} 即为 bb 的乘法逆元。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一个数组 ai,pia_i,p_i，数据保证 pip_i 是质数。

输出格式

输出共 nn 行，每组数据输出一个结果，每个结果占一行。

若 aia_i 模 pip_i 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。

样例输入

3
4 3
8 5
6 3

样例输出

1
2
impossible

题目分析

在模运算中，我们都知道，加法和乘法是比较简单的：

$$\begin{aligned} (A+B)\;\%\; mod\; = \;((A\;\%\;mod)+(B\;\%\;mod))\;\%\;mod \\ (A \times B)\;\%\; mod\; = \;((A\; \% \;mod) \times (B\; \% \;mod))\;\%\;mod \end{aligned}$$

减法因为可能由负数，所以需要加上之后再取模：

$$(A-B)\;\%\; mod\; = \;((A\;\%\;mod)-(B\;\%\;mod)+mod)\;\%\;mod$$

而除法取模则比较特别，这里我们需要引入逆元的概念。

逆元的概念

首先我们要来了解 单位元 和 逆元 的定义。

单位元

[!NOTE] 单位元的定义 在一个集合中，对于某种运算，如果对于任何的集合元素 aa，和元素 ee运算后还是得到集合元素 aa 本身，则称 ee 为这个运算下的单位元。

例如，在加法运算中，对于任意的实数 aa，都有 a+0=0+a=aa+0=0+a=a，所以加法运算的单位元 e=0e = 0。 根据上面的概念，你可以说出乘法运算的单位元是什么么？

没错，就是 11 ！

逆元

[!NOTE] 逆元的定义 在一个集合中，对于某种运算，如果任意两个元素的运算结果等于单位元，则称这两个元素互为逆元。

例如，在普通的加法运算中，任意实数 aa 的逆元为 −a-a。

同理，在普通的乘法运算中，任意实非零实数 aa 的逆元为 a−1a^{-1} 。

模乘运算下的单位元

对于结果对 nn 取模的乘法，首先所有模 nn 和 aa 同余的数都可以表示成：

a(mod  n)≡k×n+a    (k∈Z)a(mod\;n) \equiv k \times n+a \;\;(k \in Z)

假设单位元为 e(mod  n)e(mod \;n)，我们将 a(mod  n)a(mod\;n) 和 e(mod  n)e(mod\;n) 进行模乘操作，得到：

$$\begin{align*} a(mod\;n) \times e(mod \; n) &\equiv (k_{1}\ n+a)(k_{2}\ n+e)\\ &\equiv(k_{1}\ k_{2} \ n^{2}+k_{1}\ e\ n+k_{2}\ a\ n+ae)\\ &\equiv(k_{1}\ k_{2} \ n+k_{1}\ e\ n+k_{2}\ a)\ n+ae \end{align*}$$

根据单位元的定义，应该有：

a(mod  n)×e(mod  n)≡a(mod  n)a(mod\;n) \times e(mod \; n) \equiv a(mod\;n)

将上面的式子带入，则有：

$$(k_{1}\ k_{2} \ n+k_{1}\ e\ n+k_{2}\ a)\ n + ae = k \times n+a$$

所以可得：

$$\begin{cases} k_{1}\ k_{2} \ n+k_{1}\ e\ n+k_{2}\ a = k\\ \\ e = 1 \end{cases}$$

所以，模乘的单位元就是 1(mod  n)1(mod\;n)。

模乘的逆元

根据逆元的定义，若 a,na,n 互质，当 ax≡1(mod  n)ax \equiv 1(mod\;n) 时，xx 为逆元，记作 x=a−1x=a^{-1}。

例如：8x≡1(mod  5)8x \equiv 1(mod\;5)，解得 x=2,7,12…x=2,7,12 \dots，一般只考虑比 nn 小的，所以逆元为 22。

[!NOTE] 模乘逆元的定义 换个角度说，若 a,na,n 互质，并且 b∣ab|a，则存在一个整数 xx，使得 a/b≡a×x(mod  n)a/b \equiv a \times x(mod\;n)，则称 xx 为 bb 模 nn 意义下的乘法逆元，记作 b−1(mod  n)b^{-1}(mod\; n)，化简可以写成 bx≡1(mod  n)bx \equiv 1(mod\;n)。

模乘逆元的一些性质：

[!INFO] 性质

  1. 模 nn 意义，逆元一般只考虑比 nn 小的，并且在这个范围内逆元是唯一的。
  2. 逆元存在的条件，a,na,n 互质，那么 aa 在模 nn 意义下才有逆元。

这个逆元有什么用呢？在取模意义下，如果数字 aa 的逆元为 xx，那么在除以 aa 相当于 乘以 xx ，所以就把除法运算变成了乘法运算。

那么如何求出数字的模乘逆元呢？我们先来了解一下费马小定理：

[!INFO] 费马小定理 若 pp 是一个质数，且整数 aa 不是 pp 的倍数，则 ap−1≡1(mod  p)a^{p-1} \equiv 1(mod\;p)。也就是说，如果 整数 aa 不能被质数 pp 整除，那么 ap−1/pa^{p-1}/p 得到的余数是 11。

那么根据逆元的定义和费马小定理，我们可以进行如下推导：

假设 b,nb,n 互质，xx 为 bb 的模乘逆元，有：

b×x≡1(mod  n)b \times x \equiv 1(mod\;n)

根据费马小定理，有：

bn−1≡1(mod  n)b^{n-1} \equiv 1(mod\; n)

将左边式子提取一个 bb 出来，得：

b×bn−2≡1(mod  n)b \times b^{n-2} \equiv 1(mod\;n)

所以可得，逆元 x=bn−2x = b^{n-2}。

总结：

[!INFO] 费马定理求乘法逆元 若 b,nb,n 互质，且模数 nn 是质数时，bn−2b^{n-2} 即为 bb 的乘法逆元。

做法其实很简单，因为 pip_i 已经限制是质数了，只需要判断一下 ai,pia_i,p_i 是否互质，是则求 ap−2a_{p-2}，否则就是 impossible。

示例代码

int n;
cin >> n;
while (n--) {
	int a, p;
	cin >> a >> p;
	if (a%p == 0) cout << "impossible\n";
	else cout << qmi(a, p-2, p) << '\n';  // 快速幂代码和上面一致，不再演示
}

0 条评论

目前还没有评论...
98
已通过
0
题解被赞
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 74ms
  4. Powered by Hydro v5.0.0-beta.13 Community