浅谈数论技巧与科技
Cute_Fish
·
2024-09-26 19:30:44
·
个人记录
0.前言
写在前面：本文不定期更新，记录一些数论技巧与科技，主要还是蒟蒻自己复习用。
如果要完整的学习数论，不推荐看这篇文章。
不过如果只是想要了解部分知识点，可以看这篇文章。当然文章中练习的例题显然不够多，需要您自行去练习。
0.1 参考资料
参考了巨佬Alex-wei的博客，还有oiwiki。
如果想完整学习推荐看他的博客。
初等数论学习笔记 I：同余相关
初等数论学习笔记 II：分解质因数
初等数论学习笔记 III：数论函数与筛法
1.数论函数
1.1相关定义
数论函数：定义域为正整数的函数称为 数论函数。因其在所有正整数处均有定义，故可视作数列。OI 中常见的数论函数的陪域(即可能的取值范围)为整数。
积性函数：若 (p,q)=1 则 f(p,q)=f(p)f(q)。
完全积性函数：若 p,q 均在在函数定义域内则 f(p,q)=f(p)f(q)。
1.2常见数论函数
$\phi(x)=x \prod \frac{p_i-1}{p_i}$。
咕咕咕。
## 1.3一些数论函数的性质
## $\phi(ij)=\frac{\phi(i)\phi(j)gcd(i,j)}{\phi(gcd(i,j))}
\mu(ij)=\mu(i)\mu(j)[\gcd(i,j)=1]
2.筛法
2.1 线性筛积性函数
欧拉筛线性筛积性函数。
根据性质有 $f(i)=f(p_j^{c_j})f(\frac{i}{p_j^{c_j}})$。
```cpp
for(int i = 2; i < N; i++) {
if(!vis[i]) pr[++pcnt] = i, f[i] = ..., low[i] = i; // 单独算 f(p)
for(int j = 1; j <= pcnt && i * pr[j] < N; j++) {
vis[i * pr[j]] = 1;
if(i % pr[j] == 0) { // i 与 p 不互质
low[i * pr[j]] = low[i] * pr[j];
if(i == low[i]) f[i * pr[j]] = ...; // i = p ^ k，单独算 f(p ^ {k + 1})
else f[i * pr[j]] = f[i / low[i]] * f[low[i * pr[j]]];
break;
}
low[i * pr[j]] = pr[j];
f[i * pr[j]] = f[i] * f[pr[j]]; // i 与 p 互质，f(ip) = f(i)f(p)
}
}
```
## 2.2 筛莫比乌斯函数
较为简单，请读者自行理解
```cpp
int vis[N], cnt, pr[N], mu[N];
void sieve() {
mu[1] = 1;
for(int i = 2; i < N; i++) {
if(!vis[i]) pr[++cnt] = i, mu[i] = -1;
for(int j = 1; j <= cnt && i * pr[j] < N; j++) {
vis[i * pr[j]] = 1;
if(i % pr[j] == 0) break; // 此时 i * pr[j] 含至少两个 pr[j]，mu = 0
mu[i * pr[j]] = -mu[i]; // mu[i * pr[j]] = mu[i] * mu[pr[j]] = -mu[i]
}
}
}
```
## 2.3 根据狄利克雷卷积筛 $\mu
当时间复杂度可接受时，根据 \mu 的狄利克雷卷积求逆式 O(n\log n) 递推更方便。
int mu[N];
void sieve() {
mu[1] = 1;
for(int i = 1; i < N; i++)
for(int j = i + i; j < N; j += i)
mu[j] -= mu[i];
}
2.4线性筛筛欧拉函数
for(int i=2;i<=n;i++){
if(!vis[i])p[++cnt]=i,phi[i]=i-1;
for(int j=1;j<=cnt&&i*p[j]<=n;j++){
vis[i*p[j]]=1;
if(i%p[j]==0){
phi[i*p[j]]=phi[i]*p[j];
break;
}
phi[i*p[j]]=phi[i]*(p[j]-1);
}
}
2.5杜教筛
您可以在这篇文章中查看。
3. 数论分块
3.1 普通数论分块
看个题：
求 \sum _{i=1}^n \lfloor \frac{n}{i}\rfloor。
显然原式可以分成 \sqrt n 段值相等的段。
考虑已知这段的左端点 L 如何取求右端点 R。
令 \lfloor\frac{n}{L}\rfloor=T。
则 \frac{n}{R}>T,R \leq \lfloor\frac{n}{T}\rfloor。
则 R=\lfloor\frac{n}{\lfloor\frac{n}{L}\rfloor}\rfloor。
则完成上和式只需要 O(\sqrt n ) 的时间复杂度。
3.2 扩展
3.2.1 向上取整
对于 L。
尝试求出最大的 R 满足 \lceil\frac{n}{L}\rceil=\lceil\frac{n}{R}\rceil。
令 \lceil\frac{n}{L}\rceil=T。
则 \frac{n}{R} > T-1，(T-1)R 注意若 T=1 时需要特判为实际上界。 3.2.2 高维数论分块 若和式中出现若干下取整，形如 时，只需稍作修改，令 $R=min_{j=1}^c\lfloor \frac{n_j}{\lfloor\frac{n_j}{L}\rfloor}\rfloor$ 即可。 时间复杂度 $O(\sum \sqrt n_j )$。 ## 3.3 例题 [P2260](https://www.luogu.com.cn/problem/P2260) [P1403](https://www.luogu.com.cn/problem/P1403) # 4. 莫比乌斯反演 [您可以在这篇文章中查看](https://www.luogu.com.cn/article/x4swtrpi)。