【知识总结】常用的数论知识

博主： Fivk
发布时间：2022 年 02 月 26 日
1378 次浏览
暂无评论
1849字数
分类：知识总结

### 1.求最大公约数（辗转相除法）

对于两个整数`a`、`b`，我们根据辗转相除法有

$$
gcd(a, b) = gcd(b, a \% b)

故，我们可以得到以下算法

```cpp
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
```

时间复杂度$log(n)$。

### 2.算术基本定理

对于每一个整数都能被分解为多个质数乘积的形式。

$$
N=P_1^{\alpha_1}+P_2^{\alpha_2}+P_3^{\alpha_3}+...+P_k^{\alpha_k}

其中$P_i$是质数，$\alpha_i>0$

共有$\alpha_1+\alpha_2+\alpha_3+...+\alpha_k$个质因子。

比如$12=2^2\times3$、$36=2^2\times3^2$、$105=3\times5\times7$等等。

| $\varnothing$ | $P_1$ | $P2$     | $P_1$      | $P_2$        | $P_3$           |
| --------------- | ------- | ---------- | ------------ | -------------- | ----------------- |
| 1             | $P_1$ | $P_1P_2$ | $P_1^2P_2$ | $P_1^2P_2^2$ | $P_1^2P_2^2P_3$ |

可以理解为对于$a_1,a_2,a_3,...,a_t$有$a_1,\frac{a_2}{a_1},\frac{a_3}{a_2},...,\frac{a_t}{a_{t-1}}$。

#### 多重集合的排列数问题

$$
count = \frac{(\alpha_1+\alpha_2+...+\alpha_k)!}{\alpha_1!+\alpha_2!+...+\alpha_k!}

### 3.筛素数$O(n)$

> 功能：求出1 ~ n中所有质数，以及每个数的最小质因子。

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int primes[N], cnt;	// 存放所有质数
bool st[N];		// 当前数有没有被筛过
int minp[N];		// 每个数的最小质因子

int get_primes(int n) {
    for (int i = 2; i <= n; i ++) {
	if (!st[i]) minp[i] = i, primes[cnt ++] = i;
	for (int j = 0; primes[j] * i <= n; j ++) {
	    st[primes[j] * i] = true;
	    minp[primes[j] * i] = primes[j];
	    if (i % primes[j] == 0) break;
	}
    }
}

int main() {
    get_primes(10000);
    for (int i = 0; i < 20; i ++) printf("%d\n", primes[i]);
}
```

### 4.约数定理

对于任意一个正整数`N`，由于算数基本定理

$$
N=P_1^{\alpha_1}+P_2^{\alpha_2}+P_3^{\alpha_3}+...+P_k^{\alpha_k}

> 我们可以得到这个正整数`N`的约数个数为$(\alpha_1+1)(\alpha_2+1)...(\alpha_n+1)$

如$12=2^2\times3$的约束个数为$(2+1)(1+1)=6$分别为1、2、3、4、6、12。

> 我们还可以得到这个正整数`N`的约数之和为$(1+p_1+p_1^2+...+p_1^{\alpha_1})(1+p_2+p_2^2+...+p_2^{\alpha_2})...(1+p_k+p_k^2+...+p_k^{\alpha_k})$

### 5.分解质因数

> 对于一个正整数`n`中，最多只包含一个大于`sqrt(n)`的质因子

```cpp
void divide(int n) {
	for (int i = 2; i <= n / i; i ++) {
		if (n % i == 0) {
			// i 一定是质素
			int s = 0;
			while (n % i == 0) {
				n /= i;
				s ++;
			}
			printf("%d %d\n", i, s);
		}
	}
	if (n > 1) printf("%d %d\n", n, 1);
}
```

循环里面的`i` 一定是一个质数：假如 `i` 是一个合数，那么它一定可以分解成多个质因子相乘的形式，这多个质因子同时也是 `n` 的质因子且比 `i` 要小，而比 `i` 小的数在之前的循环过程中一定是被条件除完了的，所以 `i` 不可能是合数，只可能是质数。

案例：

```cpp
#include <iostream>
using namespace std;

void divide(int n) {
	for (int i = 2; i <= n / i; i ++) {
		if (n % i == 0) {
			// i 一定是质素
			int s = 0;
			while (n % i == 0) {
				n /= i;
				s ++;
			}
			printf("%d %d\n", i, s);
		}
	}
	if (n > 1) printf("%d %d\n", n, 1);
}

// 按照质因数从小到大的顺序输出每个质因数的底数和指数。
int main() {
	divide(86);
	return 0;
}
```

最后修改：2022 年 03 月 13 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

【知识总结】常用的数论知识

Fivk • 2022 年 02 月 26 日

### 1.求最大公约数（辗转相除法）

对于两个整数`a`、`b`，我们根据辗转相除法有

$$
gcd(a, b) = gcd(b, a \% b)

故，我们可以得到以下算法

```cpp
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
```

时间复杂度$log(n)$。

### 2.算术基本定理

对于每一个整数都能被分解为多个质数乘积的形式。

$$
N=P_1^{\alpha_1}+P_2^{\alpha_2}+P_3^{\alpha_3}+...+P_k^{\alpha_k}

其中$P_i$是质数，$\alpha_i>0$

共有$\alpha_1+\alpha_2+\alpha_3+...+\alpha_k$个质因子。

比如$12=2^2\times3$、$36=2^2\times3^2$、$105=3\times5\times7$等等。

可以理解为对于$a_1,a_2,a_3,...,a_t$有$a_1,\frac{a_2}{a_1},\frac{a_3}{a_2},...,\frac{a_t}{a_{t-1}}$。

#### 多重集合的排列数问题

$$
count = \frac{(\alpha_1+\alpha_2+...+\alpha_k)!}{\alpha_1!+\alpha_2!+...+\alpha_k!}

### 3.筛素数$O(n)$

> 功能：求出1 ~ n中所有质数，以及每个数的最小质因子。

```cpp
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10;
int primes[N], cnt;	// 存放所有质数
bool st[N];		// 当前数有没有被筛过
int minp[N];		// 每个数的最小质因子

int main() {
    get_primes(10000);
    for (int i = 0; i < 20; i ++) printf("%d\n", primes[i]);
}
```

### 4.约数定理

对于任意一个正整数`N`，由于算数基本定理

$$
N=P_1^{\alpha_1}+P_2^{\alpha_2}+P_3^{\alpha_3}+...+P_k^{\alpha_k}

> 我们可以得到这个正整数`N`的约数个数为$(\alpha_1+1)(\alpha_2+1)...(\alpha_n+1)$

如$12=2^2\times3$的约束个数为$(2+1)(1+1)=6$分别为1、2、3、4、6、12。

> 我们还可以得到这个正整数`N`的约数之和为$(1+p_1+p_1^2+...+p_1^{\alpha_1})(1+p_2+p_2^2+...+p_2^{\alpha_2})...(1+p_k+p_k^2+...+p_k^{\alpha_k})$

### 5.分解质因数

> 对于一个正整数`n`中，最多只包含一个大于`sqrt(n)`的质因子

案例：

```cpp
#include <iostream>
using namespace std;

// 按照质因数从小到大的顺序输出每个质因数的底数和指数。
int main() {
	divide(86);
	return 0;
}
```

【知识总结】常用的数论知识

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【Fivk】文章归档

【开发技巧】@CrossOrigin注解解决跨域问题

【Ubuntu】设置和取消代理的简易指南

【JavaWeb】HTML&CSS

【期末复习】java程序设计习题答案

【Java】注解

[函数快查] feof -- 检测文件的末尾指示器是否被设置

【Java】关键字、标识符、注释

【知识总结】常用的数论知识

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

【知识总结】常用的数论知识

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款