数论学习笔记
__KrNalty__
·
2022-06-11 19:21:07
·
个人记录
一、整除分块
1.整除分块的思想：
一个数字 n 被另一个正整数整除，得到的商只可能有根号 n 种。
简单证明：
把数字分为小于 \sqrt{n} 和大于 \sqrt{n} 两种。
所有小于 \sqrt{n} 的数字不重复时最多除出来 \sqrt{n} 个数字，所有大于 \sqrt{n} 的数字最多除出来 \sqrt{n} 个数字，所以极端情况下最多有 2\sqrt{n} 个数字。
2.相同的商，除数一定是连续的一段。例如数字 100 被 34 ~ 50 整除，得到的商都是 2.
3.假设某一段的左端点为 l ，右端点为 r ，被除数为 n ，请根据 n 和 l 的值算出 r 的值：
易知 r = n / (n / l);
4.写出循环，求出所有区间的左右端点，以及这个区间对应的商。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll l = 1, n, r;
int main()
{
cin >> n;
while (l <= n)
{
r = n / (n / l);
cout << l << " " << r << " " << n / l << endl;
l = r + 1;
}
return 0;
}洛谷习题：P2261 余数求和。
思路：1.求余没有规律，试图找一些有规律的东西，可以得如下等式：
等式中是否包含题目中所求的东西？若想得到题目中求的东西，应该如何构造？
## 二、组合数
$n$ 个数字里选 $m$ 个元素组成一个集合，方案数为 $C_n^m$，请用阶乘运算表示 $C_n^m$ 的值。
假设 $n,m$ 的数据范围为 $10^5$，如何求出对应的 $C_n^m$？（答案对 $10^9+7$ 取模）
若题目中多次询问 $C_n^m$ 的值，应该如何计算？
洛谷习题：T245093 【模板】组合数
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
ll t, n, m, f[maxn], inv[maxn], finv[maxn];
void init()
{
f[0] = 1;
for (int i = 1; i <= 1e5; i++)
{
f[i] = f[i - 1] * i % mod;
}
inv[1] = 1;
for (int i = 2; i <= 1e5; i++)
{
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
}
finv[0] = finv[1] = 1;
for (int i = 2; i <= 1e5; i++)
{
finv[i] = finv[i - 1] * inv[i] % mod;
}
}
ll C(ll n, ll m)
{
return f[n] * finv[m] % mod * finv[n - m] % mod;
}
int main()
{
init();
cin >> t;
while (t--)
{
cin >> n >> m;
cout << C(n, m) << endl;
}
return 0;
}
```
## 帕斯卡恒等式
$C_n^k = C_{n - 1}^{k - 1} + C_{n - 1}^{k}
使用递推的算法来看这个等式。从前 n 个物品里面选取其中的 k 个，有两种情况：
1.从前 n - 1 个物品里面选取其中的 k 个，第 n 个物品被忽略，在这种情况有 C_{n - 1}^k 种方式。
2.我们取用了第 n 个物品，那么从前 n - 1 个物品里面，便要选取其中的 k - 1 个，这种情况有 C_{n - 1}^{k - 1} 种方式。
加起来便是从前 n 个物品里选取其中 k 个总方式数。
杨辉三角
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...杨辉三角的第 n 行第 m 列是几？
是 C_{n - 1}^{m - 1} ，因为 C_n^x 中合法的 x 在 0 ~ n 之间，共有 n+1 种取值，和杨辉三角的第 n + 1 行对应上。
C_n^0 + C_n^1 + ... + C_n^n = ? 答: 2^n 。
C_n^0 + C_n^2 + C_n^4 + ... + C_n^n = ? 答：2^{n-1} 。
注：可用杨辉三角帮助证明。
三、异或
给定一棵树，每个节点上有一只蚂蚁。每只蚂蚁上有一只蚂蚁。每只蚂蚁都可以向上爬一格或者不爬（根节点的蚂蚁不能爬）。且每个蚂蚁都有一个属性值，若多只蚂蚁在同一个节点，则产生的快乐值是这个结点的所有蚂蚁属性值的异或。
求所有方案的所有快乐值之和。
思路：
按位算贡献。
每个节点都有多个孩子节点，这几个孩子节点与当前节点中有 x 个人二进制下第 m 位为 1，有 y 个人二进制下第 m 位为 0。我们可以进行计算使第 m 位异或后为 1 的方案数有：
$b=2^y$ （选不选 0 对结果无关，所以每一个都有选或不选两种情况）
属性值的方案数为 $2^{x-1} \times 2^y \times 2^m$。
需要再与其他无关的节点相乘，结果为 $2^{x-1} \times 2^y \times 2^m \times 2^{n-(x+y)}$。
最后进行相加即可。
## 四、因子预处理
洛谷习题：T244840 序列排序
难点：如何判断是否为 ```yes```（什么情况说明是 ```no```）
思路：
1.当某两个数不互质且大的数字在前面是 ```no``` （因为大的数字总要交换到后面去）
2.假设所有数字都是 2 的倍数，那么什么情况下是 ```no```？所有数字都是 3 的倍数，什么情况下是 ```no```？
实现 1：邻接表法。对于每个数字，将它的所有因子拿出来（需要因子预处理）。再汇总地看所有因子考虑这些因子的倍数的位置是否递增。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
vector<int>yue[maxn];
vector<int>ans[maxn];
int a, flag = 1, n, t;
void cal(){
flag = 1;
for(int i = 0; i < maxn; i++)
ans[i].clear();
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a;
for(int j = 0; j < yue[a].size(); j++)
ans[yue[a][j]].push_back(a);
}
for(int i = 2; i <= n; i++)
for(int j = 1; j < ans[i].size(); j++)
if(ans[i][j] < ans[i][j-1])
flag = 0;
if(flag) puts("Yes");
else puts("No");
}
int main(){
for(int i = 2; i < maxn; i++)
for(int j = i; j < maxn; j += i)
yue[j].push_back(i);
cin >> t;
while(t--){
cal();
}
}
```
实现 2：对于每个因子，将它的所有倍数拿出来。考虑这些倍数的位置是否递增。
```cpp
#include <bits/stdc++.h>
using namespace std;
int main(){
int t, n;
cin >> t;
while(t--){
cin >> n;
vector<int>a(n+1), pos(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i];
pos[a[i]] = i;
}
bool flag = true;
for(int i = 2; i <= n; i++){
for(int j = 2 * i; j <= n; j += i){
if(pos[j] < pos[j - i])
flag = false;
}
}
if(flag) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
```
## 五、筛法
如果我们想要知道小于等于 $n$ 有多少个素数呢？
一个自然的想法是对于小于等于 $n$ 的每个数进行一次质数检验。这种暴力的做法显然不能达到最优复杂度。
### 埃氏筛：
考虑这样一件事情：对于任意一个大于 $1$ 的正整数 $n$，那么它的 $x$ 倍就是合数（$x>1$）。利用这个结论，我们可以避免很多次不必要的检测。
如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。
```cpp
int Eratosthenes(int n) {
int p = 0;
for (int i = 0; i <= n; ++i) is_prime[i] = 1;
is_prime[0] = is_prime[1] = 0;
for (int i = 2; i <= n; ++i) {
if (is_prime[i]) {
prime[p++] = i; // prime[p]是i,后置自增运算代表当前素数数量
if ((long long)i * i <= n)
for (int j = i * i; j <= n; j += i)
// 因为从 2 到 i - 1 的倍数我们之前筛过了，这里直接从 i
// 的倍数开始，提高了运行速度
is_prime[j] = 0; // 是i的倍数的均不是素数
}
}
return p;
}
```
可以证明这个方法的时间复杂度是 $O(n\log n) $ 的。
### 线性筛：
埃氏筛法仍有优化空间，它会将一个合数重复多次标记。有没有什么办法省掉无意义的步骤呢？答案是肯定的。
如果能让每个合数都只被标记一次，那么时间复杂度就可以降到 $O(n)$ 了。
```cpp
void init() {
for (int i = 2; i < MAXN; ++i) {
if (!vis[i]) {
pri[cnt++] = i;
}
for (int j = 0; j < cnt; ++j) {
if (1ll * i * pri[j] >= MAXN) break;
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) {
// i % pri[j] == 0
// 换言之，i 之前被 pri[j] 筛过了
// 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定也是
// pri[j] 的倍数 它们都被筛过了，就不需要再筛了，所以这里直接 break
// 掉就好了
break;
}
}
}
}
```
## 六、快速幂
快速幂，二进制取幂（Binary Exponentiation，也称平方法），是一个在 $O(\log n)$ 的时间内计算 $a^n$ 的小技巧，而暴力的计算需要 $O(n)$ 的时间。而这个技巧也常常用在非计算的场景，因为它可以应用在任何具有结合律的运算中。其中显然的是它可以应用于模意义下取幂、矩阵幂等运算，我们接下来会讨论。
### 算法描述：
计算 $a$ 的 $n$ 次方表示将 $n$ 个 $a$ 乘在一起：$a^n=\begin{matrix}\underbrace{a\times a \times \cdots \times a}\\n\text{个}a\end{matrix}$。然而当 $n$ 太大的时侯，这种方法就不太适用了。不过我们知道：$a^{b+c} =a^b \cdot a^c, a^{2b}=a^b\cdot a^b=(a^b)^2$。二进制取幂的想法是，我们将取幂的任务按照指数的 **二进制表示** 来分割成更小的任务。
首先我们将 $n$ 表示为 2 进制，举一个例子：
$$3^{13}=3^{(1101)_2}=3^8\cdot 3^4 \cdot 3^1$$
因为 $n$ 有 $\left\lfloor{\log_2 n}\right\rfloor + 1$ 个二进制位，因此当我们知道了 $a^1,a^2,a^4,a^8,\cdots,a^{\left\lfloor{\log_2 n}\right\rfloor}$ 后，我们只用计算 $O(\log n)$ 次乘法就可以计算出 $a^n$。
于是我们只需要知道一个快速的方法来计算上述 3 的 $2^k$ 次幂的序列。这个问题很简单，因为序列中（除第一个）任意一个元素就是其前一个元素的平方。举一个例子：
$$3^1 =3 $$
$$3^2 = (3^1)^2 = 3^2 = 9$$
$$3^4=(3^2)^2 = 9^2=81$$
$$3^8 = (3^4)^2=81^2=6561$$
因此为了计算 $3^{13}$，我们只需要将对应二进制位为 1 的整系数幂乘起来就行了：
$$3^{13}=6561\cdot81\cdot3=1594323$$
将上述过程说得形式化一些，如果把 $n$ 写作二进制为 $(n_tn_{t-1}\cdots n_1n_0)_2$，那么有：
$$n=n_t2^t+n_{t-1}2^{t-1}+n_{t-2}2^{t-2}+\cdots+n_12^1+n_02^0$$
其中 $n_i \in \{0,1\}$（$n_i$ 是 0 或 1）。那么就有：
$$a^n=a^{n_t2^t+\cdots+n_02^0}=a^{n_02^0} \times a^{n_12^1} \times \cdots \times a^{n_t2^t}$$
根据上式我们发现，原问题被我们转化成了形式相同的子问题的乘积，并且我们可以在常数时间内从 $2^i$ 项推出 $2^{i+1}$ 项。
这个算法的复杂度是 $O(\log n)$ 的，我们计算了 $O(\log n)$ 个 $2^k$ 次幂的数，然后花费 $O(\log n)$ 的时间选择二进制为 1 对应的幂来相乘。
### 简单来说：
想要得到 $a^n$ 的值，可以先算出 $a^{\left\lfloor\frac{n}{2}\right\rfloor}$ 的值。
1.如果 $n$ 是偶数，则 $a_n=a^{\left\lfloor\frac{n}{2}\right\rfloor}\cdot a^{\left\lfloor\frac{n}{2}\right\rfloor}$。
2.如果 $n$ 是奇数，则 $a_n=a^{\left\lfloor\frac{n}{2}\right\rfloor}\cdot a^{\left\lfloor\frac{n}{2}\right\rfloor}\cdot a$。
于是我们每次都只需要算出 $a^{\left\lfloor\frac{n}{2}\right\rfloor}$ 的值，时间复杂度 $O(\log n)$。
**实现 1：**
可以直接按照上述递归方法实现：
```cpp
long long binpow(long long a, long long b) {
if (b == 0) return 1;
long long res = binpow(a, b / 2);
if (b % 2)
return res * res * a;
else
return res * res;
}
```
**实现 2：**
第二种实现方法是非递归式的。它在循环的过程中将二进制位为 1 时对应的幂累乘到答案中。尽管两者的理论复杂度是相同的，但第二种在实践过程中的速度是比第一种更快的，因为递归会花费一定的开销。
```cpp
long long binpow(long long a, long long b) {
long long res = 1;
while (b > 0) {
if (b & 1) res = res * a;
a = a * a;
b >>= 1;
}
return res;
}
```
## 七、欧拉函数
$\varphi(x)$ 为小于等于 $x$ 的所有正整数中与 $x$ 互质的数字的个数，即欧拉函数研究的问题。
#### 想一想
30000 以内有多少个和 30000 互质的数字？
#### 欧拉函数的计算
假设 $x$ 的素因子分解为 $x = p_1^{k_1} \times p_2^{k_2} \times \cdots \times p_n^{k_n}
则 \varphi(x)= x \times (1-\frac{1}{p_1}) \times (1-\frac{1}{p_2})\times\cdots\times(1-\frac{1}{p_n})
试证明理解
计算一下 \varphi(10007) ？（提示：10007 是一个质数）
计算一下 \varphi(30000) ？
欧拉函数的递推
考虑某一个数字 a=xy ，其中 y 是 a 的最小质因子。
那么 \varphi(xy) = \begin{cases}\varphi(x)\times \varphi(y)& \text{if\ gcd}(x,y)=1, \\ \varphi(x)\times y & \text{if\ } x \text{ 是 } y \text{ 的倍数}.\end{cases}
试证明。
想一想
递推的前提是 y 是 a 的最小质因子，这个条件有什么用呢？
代码
bool vis[maxn];
int prime[maxn], f[maxn];
void init() {
int cnt = 0; // 目前已经发现的素数个数
for(int i = 2; i < maxn; i++) {
if(!vis[i]){
prime[++cnt] = i;
f[i] = i - 1;
}
for(int j = 1; j <= cnt && i * prime[j] < maxn; j++) {
vis[prime[j] * i] = 1;
if(i % prime[j] == 0){
f[prime[j] * i] = f[i] * prime[j];
break;
}else{
f[prime[j] * i] = f[prime[j]] * f[i];
}
}
}
}洛谷习题：P2158 仪仗队
位于 a,b 的人需要满足什么条件才能被看见？试写出暴力代码。