数论专题 II
题单介绍
[LaTeX 数学公式大全](https://www.luogu.com.cn/blog/IowaBattleship/latex-gong-shi-tai-quan)
### 简介
本题单会更注重推式子能力。
包含了关于数论分块，欧拉函数，莫比乌斯函数，杜教筛的题目。
### 【广告】
我的其他数学题单。
- [我的数论专题I](https://www.luogu.com.cn/training/234164)
### 学习资料
- [数论函数小结](https://www.luogu.com.cn/blog/205125/shuo-lun-han-shuo-xiao-jie)
- [数学数论第一章之学会推式子](https://www.luogu.com.cn/blog/ternaryTree/shuo-xue-shuo-lun-xiang-guan)
- [数学数论第二章之手把手教你同余方程](https://www.luogu.com.cn/blog/ternaryTree/shuo-xue-shuo-lun-di-er-zhang-zhi-shou-ba-shou-jiao-ni-tong-yu-fang-ch)
- [莫比乌斯反演-让我们从基础开始](https://www.luogu.com.cn/blog/An-Amazing-Blog/mu-bi-wu-si-fan-yan-ji-ge-ji-miao-di-dong-xi)
- [莫比乌斯反演-从莫比乌斯到欧拉](https://www.luogu.com.cn/blog/An-Amazing-Blog/ji-miao-di-mu-bi-wu-si-fan-yan)
- [【数论】狄利克雷卷积&莫比乌斯反演 学习笔记](https://www.luogu.com.cn/blog/C-liar/post-shuo-lun-di-li-ke-lei-juan-ji-mu-bi-wu-si-fan-yan-xue-xi-bi-ji)
- [铃悬的数学小讲堂——狄利克雷卷积与莫比乌斯反演](https://www.luogu.com.cn/blog/lx-2003/mobius-inversion)
- [铃悬的数学小讲堂——杜教筛](https://www.luogu.com.cn/blog/lx-2003/dujiao-sieve)
- [浅谈莫反](https://www.luogu.com.cn/blog/257146/qian-tan-mo-fan)
- [cmd的莫比乌斯反演与数论函数](https://www.luogu.com.cn/blog/command-block/mu-bi-wu-si-fan-yan-ji-ji-ying-yong)
### 练习题单
- [别人的欧拉函数题单](https://www.luogu.com.cn/training/7052)
- [莫比乌斯反演（函数）练习题单](https://www.luogu.com.cn/training/1055)
- [数学数论之推式子](https://www.luogu.com.cn/training/200296)
- [莫反](https://www.luogu.com.cn/training/131971)
- [莫比乌斯反演与各种筛法题单](https://www.luogu.com.cn/training/81332)
## 数论分块
数论分块又称整除分块，是一种加速计算的小技巧，在之后的题目中不可或缺。
- [我的数论分块讲解](https://www.luogu.com.cn/blog/205125/shuo-lun-fen-kuai)
- [浅谈数论分块](https://www.luogu.com.cn/blog/486187/awawawa)
### 题目
- [UVA11526 H(n)](https://www.luogu.com.cn/problem/UVA11526)
- [P1403 [AHOI2005]约数研究](https://www.luogu.com.cn/problem/P1403)
- [P2261 [CQOI2007]余数求和](https://www.luogu.com.cn/problem/P2261)
- [P2424 约数和](https://www.luogu.com.cn/problem/P2424)
- [P3935 Calculating](https://www.luogu.com.cn/problem/P3935)
- [P2260 [清华集训2012]模积和](https://www.luogu.com.cn/problem/P2260)
- [P6788 「EZEC-3」四月樱花](https://www.luogu.com.cn/problem/P6788)
---
## 欧拉函数
欧拉函数和欧拉反演可以让我们开始推式子。
### 定义
$\varphi(n)$ 表示在 $1\sim n$ 中与 $n$ 互质的数
$\displaystyle\varphi(n)=\sum_{i=1}^{n}[gcd(i,n)=1]$
### 计算
详细证明见：[这里](https://www.luogu.com.cn/blog/205125/shuo-lun-han-shuo)。
$\displaystyle\varphi (n)=n\prod\limits_{i=1}^{s} (1- \frac{1}{p_1})$
其中 $n={p_1}^{a_1}{p_2}^{a_2}\dots{p_s}^{a_s}$ 是 $n$ 的标准分解
时间复杂度 $\mathcal{O(\sqrt{n})}$
#### 性质：欧拉筛
若 $p\mid n$ 且 $p^2\mid n$ ，$\varphi(n)=\varphi(\frac{n}{p})*p$
若 $p\mid n$ 且 $p^2\nmid n$ ，$\varphi(n)=\varphi(\frac{n}{p})*(p-1)$
#### 性质：欧拉反演
对于任意 $n$ ，有
$\displaystyle n=\sum_{d\mid n}\varphi(d)$
### 欧拉函数和欧拉反演
- [SP4141 ETF - Euler Totient Function](https://www.luogu.com.cn/problem/SP4141)
- [UVA10179 Irreducable Basic Fractions](https://www.luogu.com.cn/problem/UVA10179)
- [P3601 签到题](https://www.luogu.com.cn/problem/P3601)
- [P2350 [HAOI2012]外星人](https://www.luogu.com.cn/problem/P2350)
- [P3166 [CQOI2014]数三角形](https://www.luogu.com.cn/problem/P3166)
- [P2158 [SDOI2008] 仪仗队](https://www.luogu.com.cn/problem/P2158)
- [P2398 GCD SUM](https://www.luogu.com.cn/problem/P2398)
- [P2303 [SDOI2012] Longge 的问题](https://www.luogu.com.cn/problem/P2303)
- [P1447 [NOI2010] 能量采集](https://www.luogu.com.cn/problem/P1447)
- [P1891 疯狂 LCM](https://www.luogu.com.cn/problem/P1891)
---
#### 前置芝士：狄利克雷卷积
- [P5495 Dirichlet 前缀和](https://www.luogu.com.cn/problem/P5495)
[Dirichlet 前缀和讲解](https://www.cnblogs.com/LanternFestival/p/15376325.html)
## 莫比乌斯函数
莫比乌斯函数有很多灵活应用，广泛运用于推式子。
莫比乌斯函数 $\mu(n)$ 的定义为：
$\mu(n)= \begin{cases} 1&n=1\\ (-1)^s&n=p_1 p_2 \dots p_s\\ 0&\text{otherwise} \end{cases}$
其中 $p_1 , p_2 \dots p_s$ 为不同的质数。
对于任意正整数 $n$ ，有 $\sum\limits_{d|n}\mu(d)=\epsilon (n)$。
写成狄利克雷卷积的形式即为 $\mu * 1=\epsilon $。
### 莫比乌斯变换
若 $g(n)=\sum\limits_{d|n}f(d)$，
则称 $g$ 为 $f$ 的 **莫比乌斯变换** ，$f$ 为 $g$ 的**莫比乌斯逆变换**。
写成狄利克雷卷积的形式即为 $g=f * 1$。
### 莫比乌斯反演定理
莫比乌斯反演定理指出，上式的充要条件为 $f(n)=\sum\limits_{d|n}g(d)\mu(\frac{n}{d})$。
写成狄利克雷卷积形式即为 $f=g*\mu$。
### 题目
- [P2257 YY的GCD](https://www.luogu.com.cn/problem/P2257)
- [P1390 公约数的和](https://www.luogu.com.cn/problem/P1390)
- [P3455 [POI2007]ZAP-Queries](https://www.luogu.com.cn/problem/P3455)
- [P2522 [HAOI2011]Problem b](https://www.luogu.com.cn/problem/P2522)
- [P4450 双亲数](https://www.luogu.com.cn/problem/P4450)
- [P6810 「MCOI-02」Convex Hull 凸包](https://www.luogu.com.cn/problem/P6810)
- [P1829 [国家集训队]Crash的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)
- [P3911 最小公倍数之和](https://www.luogu.com.cn/problem/P3911)
- [P5221 Product](https://www.luogu.com.cn/problem/P5221)
- [P3327 [SDOI2015]约数个数和](https://www.luogu.com.cn/problem/P3327)
- [P6156 简单题](https://www.luogu.com.cn/problem/P6156)
- [P4449 于神之怒加强版](https://www.luogu.com.cn/problem/P4449)
- [P6825 「EZEC-4」求和](https://www.luogu.com.cn/problem/P6825)
- [P3312 [SDOI2014]数表](https://www.luogu.com.cn/problem/P3312)
- [CF439E Devu and Birthday Celebration](https://www.luogu.com.cn/problem/CF439E)
- [CF1139D Steps to One](https://www.luogu.com.cn/problem/CF1139D)
- [CF645F Cowslip Collections](https://www.luogu.com.cn/problem/CF645F)
```cpp
const int N=1e6+5;
typedef long long ll;
ll phi[N],mu[N],prime[N];
ll sumphi[N],summu[N];
bool isprime[N];
int n,cnt;
void init(){
phi[1]=mu[1]=1;
for(int i=2;i<=n;i++){
if(!isprime[i]){
prime[++cnt]=i;
phi[i]=i-1,mu[i]=-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
isprime[i*prime[j]]=1;
if(!(i%prime[j])){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
phi[i*prime[j]]=phi[i]*(prime[j]-1);
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1;i<=n;i++){
sumphi[i]=sumphi[i-1]+phi[i];
summu[i]=summu[i-1]+mu[i];
}
}
```
---
## 欧拉定理和扩展欧拉定理
欧拉定理和扩展欧拉定理可以有效降低幂次，方便运算。
#### 欧拉定理
当 $a,m\in \mathbb{Z}$，且 $\gcd(a,m)=1$ 时有：
$a^{\varphi(m)}\equiv 1\pmod{m}$
所以 $a^b\equiv a^{b\bmod \varphi(m)}\pmod m$
#### 扩展欧拉定理：
当 $a,m\in \mathbb{Z}$ 时有：
$a^b\equiv\left\{\begin{matrix}a^b&,b<\varphi(m)\\a^{b\bmod\varphi(m)+\varphi(m)}&,b\ge\varphi(m)\end{matrix}\right.\pmod m$
### 题目
- [P5091 【模板】扩展欧拉定理](https://www.luogu.com.cn/problem/P5091)
- [P4139 上帝与集合的正确用法](https://www.luogu.com.cn/problem/P4139)
- [P3747 [六省联考 2017] 相逢是问候](https://www.luogu.com.cn/problem/P3747)
- [CF906D Power Tower](https://www.luogu.com.cn/problem/CF906D)
- [P3934 [Ynoi2016] 炸脖龙 I](https://www.luogu.com.cn/problem/P3934)
---
## 杜教筛
欧拉函数非线性筛法，但注意要与莫比乌斯函数同筛，需要一定反演知识。
- [P4213 【模板】杜教筛（Sum）](https://www.luogu.com.cn/problem/P4213)
- [SP19985 GCDEX2 - GCD Extreme (hard)](https://www.luogu.com.cn/problem/SP19985)
- [P3768 简单的数学题](https://www.luogu.com.cn/problem/P3768)
- [P6055 [RC-02] GCD](https://www.luogu.com.cn/problem/P6055)
- [P4318 完全平方数](https://www.luogu.com.cn/problem/P4318)