知识点 - 数论进阶

abstract：整除分块，积性函数，线性筛，莫比乌斯反演，迪利克雷卷积，积性函数前缀和，杜教筛，阁洲筛，min_25筛

0.引入

Gym - 101485D debugging

（之后会发现，这道dp的转移方程和杜教筛的转移如出一辙。）

题意

有一份包含1个 bug 的n( 1≤?≤1e6)行代码，运行一次到崩溃需要的时间为 r( 1≤?≤1e9)。

你可以任意行添加 printf 语句来输出调试，即你知道是否在执行 printf 语句前就崩溃了。每设置一个 printf 语句需要花费 p( 1≤?≤1e9)时间，但是运行不额外消耗。
• 问在最坏情况下，少需要多时间可以定位

分析

设f(n) 表示 n行代码 debug 需要的最少时间 。

最优策略是平均地往n行代码添加x行输出代码，分成$\lceil \frac{n}{x+1}\rceil$块代码，然后再对出错的上一块代码递归debug.

得到对应的转移：
$$\begin{gathered} f(1)=0; \\ f(n)=mi{n}_{1\le i<n}(f(\lceil \frac{n}{i+1}\rceil )+ip+r) \end{gathered}$$
这个$O(n^2)$的转移可以利用整除分块优化。

复杂度

递归过程中会出现$\lceil \frac{\lceil \frac{n}{i}\rceil }{j}\rceil$的式子，但我们有
$$\lceil \frac{\lceil \frac{n}{i}\rceil }{j}\rceil =\lceil \frac{n}{ij}\rceil$$
所以递归中所有的取值都是$\lceil \frac{n}{i}\rceil$的形式，而$\lceil \frac{n}{i}\rceil$的取值只有$\sqrt{n}$种，所以我们枚举$\sqrt{n}$并记忆化搜索。时间复杂度为：
$$\begin{gathered} T(n)=O(\sqrt{n})+\sum _{i=1}^{\sqrt{n}}T(i)+T(\frac{n}{i}) \\ T(n)=\sum _{i=1}^{\sqrt{n}}O(\sqrt{i})+O(\sqrt{\frac{n}{i}})=O(n^{\frac{3}{4}}) \end{gathered}$$
这里只展开一层就可以了，更深层的复杂度是高阶小量

小结

递归式形如
$$f(n)=mi{n}_{1\le i<n}(f(\lceil \frac{n}{i+1}\rceil )+ip+r)$$
可以利用整除分块做到$O(n^{\frac{3}{4}})$。

这种形式的递归会在后面求积性函数前缀和时出现。

1.phi & mu：积性函数

定义

积性函数：若m1,m2互质
$$f(m1m2)=f(m1)f(m2)$$

性质

1. 积性函数只由其在质数幂处的取值决定。（这是积性函数可以线性筛的原因,线性筛素数模板如下）

   for (int i = 2; i <= n; i++)
   {
   	if (!vis[i])
   		prime[cnt++] = i;
   	for (int j = 0;; j++)
   	{
   		int x = i * prime[j];
   		if (x>n)
   			break;
   		vis[x] = true;
   		if (i%prime[j] == 0)
   			break;
   	}
   }
   

2. 定义约数函数和sum-over-divisors function （迪利克雷卷积的原型）
   $$g(n)=\sum _{d|n}f(d)$$
   若f是积性函数，则g是积性函数

3. phi可以这么定义
   $$\varphi (d):\sum _{d|n}\varphi (d)=n$$
   反过来可以用最简分数统计个数证明，即
   $$\begin{gathered} \frac{0}{12},\frac{1}{12},\frac{2}{12},\frac{3}{12},\frac{4}{12},\frac{5}{12},\frac{6}{12},\frac{7}{12},\frac{8}{12},\frac{9}{12},\frac{10}{12},\frac{11}{12} \\ \frac{0}{1};\frac{1}{2};\frac{1}{3},\frac{2}{3};\frac{1}{4},\frac{3}{4};\frac{1}{6},\frac{5}{6};\frac{1}{12},\frac{5}{12},\frac{7}{12},\frac{11}{12} \\ \varphi (1)+\varphi (2)+\varphi (3)+\varphi (4)+\varphi (6)=12 \end{gathered}$$

4. mu可以这么定义
   $$\mu (d):\sum _{d|n}\mu (d)=[n=1]$$
   反过来可以看作是容斥的系数证明,即

$$\sum _{d|n}\mu (d)=\sum _{i=0}^{k}C(k,i)\cdot (-1{)}^i=(1-1{)}^k=0$$

5. mu的性质：
   $$g(n)=\sum _{d|n}f(d)\leftrightarrow f(n)=\sum _{d|n}g(\frac{n}{d})\mu (d)$$
   A.K.A.莫比乌斯反演

常见积性函数

1. $\tau (n)={\sigma }_0(n)={\sum }_{d|n}1$ 约数个数
2. $\sigma (n)={\sigma }_1(n)={\sum }_{d|n}d$ 约数和
3. ${\sigma }_k(n)={\sum }_{d|n}{d}^k$ 约数和的k次幂
4. $e(n)=[n=1]$
5. $I(n)=1$ 恒等函数
6. $id(n)=n$
7. $i{d}^k(n)=n^k$

2.迪利克雷卷积

定义

$$(f\ast g)(n)=\sum _{d|n}f(d)\cdot g(\frac{n}{d})=\sum _{ij=n}f(i)\cdot g(j)$$

（可以类比多项式乘法的卷积，n次项系数为$h(n)={\sum }_{i+j=n}f(i)\cdot g(j)$）

性质

1. 交换律、结合律，对加法满足分配律

2. 若f和g为积性，则$f\ast g$ 积性

3. $e(n)=[n=1]$是单位元
   $$f\ast e=f=e\ast f$$

4. 莫比乌斯函数与恒等函数互为逆元，即
   $$\begin{gathered} \mu \ast I=e \\ g=f\ast I\leftrightarrow f=g\ast \mu \\ (\because g\ast \mu =f\ast I\ast \mu ) \end{gathered}$$

5. 上面的结论就是莫比乌斯反演的卷积版，已知g时，用来求f

6. 试对欧拉函数用莫比乌斯反演得到：
   $$\begin{gathered} \because \varphi \ast I=id \\ \therefore \varphi =id\ast \mu \end{gathered}$$
   展开移项得到：
   $$\frac{\phi (n)}{n}=\sum _{d|n}\frac{\mu (d)}{d}$$

7. 狄利克雷卷积的一个常用技巧是对于积性函数$f$与恒等函数$I$的卷积的处理:
   $$\begin{gathered} n=\prod _{i=1}^t{p}_i^{k_i},g(n)=\sum _{d|n}f(d) \\ g(n)=\prod _{i=1}^t\sum _{j=0}^{k_i}f(p_i^j) \end{gathered}$$

3.历年题目

HDU - 5528 ICPC 2015 长春 B

7738 - Fibonacci ICPC 2016 青岛 E 结论生僻

最大公约数 CCPC 2016 合肥 J

Just a Math Problem CCPC 2016 杭州 J

Cow`s Segment CCPC 2017 harbin I

Mod, Xor and Everything CCPC 2017 杭州L 难

4.例题

例题1 积性函数&迪利克雷卷积应用

HDU - 5528 ICPC 2015 长春 B

题意

定义 $f(n)=$选两个 $[0,n) $的整数$ a,b$ ，且 ab不是n的倍数方案。
求$g(n)={\sum }_{d|n}f(d)$

分析

由题意得到:
$$f(n)=n^2-\sum _{d|n}\varphi (\frac{n}{d})\cdot d$$
这个式子可以这么理解，首先求问题的反面，即$n|ab$的方案数。 当$a=k\cdot j$时，$b$必须取与 $ i=n/j$ 互质的数。$a$的取值有$n/j$种，$b$的取值有$\varphi (i)$种，有
$$\sum _{ij=n}\varphi (i)\cdot j=\sum _{d|n}\varphi (\frac{n}{d})\cdot d$$
设
$$h(n)=\sum _{d|n}\varphi (\frac{n}{d})\cdot d$$
有
$$g(n)=\sum _{d|n}f(d)=\sum _{d|n}(d^2-h(d))$$
设
$$P(n)=\sum _{d|n}{d}^2,Q(n)=\sum _{d|n}h(d)$$
根据积性函数的性质，求单个$P(n),Q(n)$,我们只需要计算 $P(p^k),Q(p^k)$乘起来就可以得到 $P(n),Q(n)$。而这是很容易计算的，因为 $p^k$的因数只有$p^0,p^1,\cdots ,p^k$。（这也是线性筛的原理）

剩下的是质因数分解的复杂度$O(\frac{\sqrt{n}}{\ln \sqrt{n}})$，证明在质数知识点里讨论过。

其实$Q(n)$可以进一步化简：
$$\begin{gathered} Q(n)=\sum _{d|n}h(d)=Q(n)=\sum _{d|n}\sum _{w|d}\varphi (w)\cdot \frac{d}{w} \\ =I\ast \varphi \ast id=id\ast id=\sum _{d|n}d\cdot \frac{n}{d}=n\cdot \sum _{d|n}1=n\cdot \tau (n) \end{gathered}$$

例题2 积性函数递推性质

题意

定义$f_0(n)$为满足??=?且gcd（?,?）=1的对数。

定义
$$f_{r+1}=\sum _{uv=1}\frac{f_r(u)+f_r(v)}{2}$$
q组询问$f_r(n)$ q,r,n<1e6

分析

定义$\omega (n)$为n的不同质因子g个数，则$f_0=2^{\omega (n)}$.

注意到$f_r$为积性，所以$f_{r+1}$也为积性.

由于积性，我们只需要求$f_r(p^k)$.

注意到$\forall p,f_0(p)=2$，所以$\forall p,f_r(p^k)$是定值如果r，k是定值。

又注意到k是O(logn)的，前缀和优化求$f_{r+1}(p^k)={\sum }_{i=0}^k{f}_r(p^i)$,使用O(rlogn)的时间预处理出所有可能的$f_r(p^k)$的询问。

剩下质因数分解的复杂度。

例题3 积性函数前缀和

题意

四川省赛grisaia
$$ans=\sum _{i=1}^n\sum _{j=1}^i(nmod(i\times j))$$
$1\le n\le 10^{11}$

分析

如果 f§可以在 O(logn)的时间内求出来，求出质数项的总时间是?(?)的；

通常，f(pk)可以比较容易的由$f(p^{k-1})$等值递推出来。其他项可以直接由积性函数的性质$f(x)=f(d)\ast f(\frac{x}{d})$得到。因此，很多积性函数都可以在欧拉筛的过程中顺便递推出，很多积性函数都可以在欧拉筛的过程中顺便递推出前 ?项的值，时间复杂度为 ?(?)。

此题要求低于线性时间前缀和。

解法1

公式推导：
$$ans=\sum _{i=1}^n\sum _{j=1}^i(nmod(i\times j))=\sum _{i=1}^n\sum _{j=1}^i(n-\lfloor n/ij\rfloor \cdot ij)$$
而
$$\sum _{i=1}^n\sum _{j=1}^i\lfloor \frac{n}{ij}\rfloor \cdot ij=(\sum _{i=1}^n\sum _{j=1}^n\lfloor \frac{n}{ij}\rfloor \cdot ij+\sum _{i=1}^n\lfloor \frac{n}{i^2}\rfloor i^2)/2$$
令a=${\sum }_{i=1}^n{\sum }_{j=1}^n\lfloor \frac{n}{ij}\rfloor \cdot ij$, $f(n)={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor i$则
$$\begin{gathered} a=\sum _{i=1}^n\sum _{j=1}^{n}i\cdot \lfloor \frac{\lfloor \frac{n}{i}\rfloor }{j}\rfloor \cdot j \\ =\sum _{i=1}^{n}i\sum _{j=1}^n\lfloor \frac{\lfloor \frac{n}{i}\rfloor }{j}\rfloor \cdot j \\ =\sum _{i=1}^{n}i\cdot f(\lfloor \frac{n}{i}\rfloor ) \end{gathered}$$
$O(\sqrt{n})$地枚举$\lfloor \frac{n}{i}\rfloor$,然后$O(\sqrt{\lfloor \frac{n}{i}\rfloor })$ 地计算$f(\lfloor \frac{n}{i}\rfloor )$时间复杂度为
$$O(\sum _{i=1}^{\sqrt{n}}\sqrt{\lfloor \frac{n}{i}\rfloor })=O(n^{\frac{3}{4}})$$
O(1)读写f的技巧：用两个$\sqrt{n}$大小的数组。

解法2

定义g(n)=f(n)-f(n-1),
$$g(n)=\sum _{i=1}^{n}i\cdot (\lfloor \frac{n}{i}\rfloor -\lfloor \frac{n-1}{i}\rfloor )=\sum _{i|n}i$$
求其前$n^{\frac{2}{3}}$项及其前缀和。对于$\lfloor \frac{n}{i}\rfloor >n^{\frac{2}{3}}$暴力计算$f(\lfloor \frac{n}{i}\rfloor )$,复杂度为
$$O(\sum _{i=1}^{n^{\frac{1}{3}}}\sqrt{\lfloor \frac{n}{i}\rfloor })=O(n^{\frac{2}{3}})$$

例题4 莫比乌斯反演

题意

YY的GCD
$$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^m[gcd(i,j)=p] \\ (n,m⩽1e7) \end{gathered}$$

分析

将p提出来，
$$ans=\sum _{i=1}^{\lfloor \frac{n}{p}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{p}\rfloor }[gcd(i,j)=1]$$
根据容斥
$$\left|\bigcup _{i=1}^n{A}_i\right|=\sum _{\varnothing \ne J\subseteq \{1,2,\dots ,n\}}(-1{)}^{|J|-1}|\bigcap _{j\in J}{A}_j|$$
得到
$$\begin{gathered} ans=\sum _p{\sum }_{d=1}^{\lfloor \frac{min(m,n)}{p}\rfloor }\mu (d)\lfloor \frac{n}{pd}\rfloor \lfloor \frac{m}{pd}\rfloor \\ =\sum _{i=1}^{min(n,m)}\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor \sum _{p|i}\mu \left(\frac{i}{p}\right) \end{gathered}$$
定义
$$f(i)=\sum _{p|i}\mu \left(\frac{i}{p}\right)$$
则
$$ans=\sum _{i=1}^{min(n,m)}\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor f(i)$$
预处理f即可$O(\sqrt{n}+\sqrt{m})$地回答每组询问.

若暴力求f，复杂度$O(nloglogn)$

观察得到递推式：

设x为n的最小质因子，若$x^2|n,f(n)=\mu (n/x)$否则：
$$f(n)=\mu (n/x)+\mu (x)f(n/x)=\mu (n/x)-f(n/x)$$
用线性筛做到O(n)

例题5 杜教筛求数论函数前缀和

分析

如果能通过狄利克雷卷积构造一个更好计算前缀和的函数，且用于卷积的另一个函数也易计算，则可以简化计算过程。

具体来说，设S(n)为f(n)的前缀和.$\forall$数论函数 $g$ ，设$h=f\ast g$,有
$$\begin{gathered} \sum _{i=1}^{n}h(i)=\sum _{i=1}^n\sum _{d|i}f(d)\cdot g(\frac{i}{d}) \\ =\sum _{i=1}^{n}g(i)S(\lfloor \frac{n}{i}\rfloor ) \end{gathered}$$
移项得
$$g(1)S(n)=\sum _{i=1}^{n}h(i)-\sum _{i=2}^{n}g(i)S(\lfloor \frac{n}{i}\rfloor )$$
对于可以$O(\sqrt{n})$求h前缀和，$O(1)$求g的情况，复杂度为$O({\sum }_{i=1}^{\sqrt{n}}\sqrt{\lfloor \frac{n}{i}\rfloor })=O(n^{\frac{3}{4}})$.

如果f有较好的性质（比如积性函数），可以线性筛求其前$n^{\frac{2}{3}}$项,$>n^{\frac{2}{3}}$递归计算，复杂度为$O(n^{\frac{2}{3}})$

题意

【模板】杜教筛（Sum）

blog
$$\begin{gathered} \sum _{i=1}^n\phi (i) \\ \sum _{i=1}^n\mu (i) \end{gathered}$$

hdu 5608 function

huntian oy 杜教筛进阶

blog
$$
n^{2-3n+2=\sum_{d|n}f(d),求\sum_{i=1}}nf(i)\ mod \ 10^9+7\\ \

\sum_{i=1}^n\varphi(i)*i
$$

divcnt3 阁洲筛/扩展欧拉筛ees

2016年数论函数论文

blog 类欧几里得
$$S_3(n)=\sum _{i=1}^n{\sigma }_0(i^3).$$

Just a Math Problem CCPC 2016 杭州 J

非套路线性求和,令$\omega (n)$为质因数个数。
$$\sum _{i=1}^n{2}^{\omega (n)}$$
more exe:

51Nod 1244 - 莫比乌斯函数之和
51Nod 1239 - 欧拉函数之和
BZOJ 3944 - Sum
HDU 5608 - function
51Nod 1238 - 最小公倍数之和 V3
51Nod 1237 - 最大公约数之和 V3
51Nod 1227 - 平均最小公倍数
Tsinsen A1231 - Crash的数字表格
SPOJ DIVCNT2 - Counting Divisors (square)
51Nod 1222 - 最小公倍数计数（复杂度分析）
BZOJ 4176 - Lucas的数论
51Nod 1220 - 约数之和
51Nod 1584 - 加权约数和
ZOJ 3881 - From the ABC conjecture（不需要使用正文方法）
BZOJ 3512 - DZY Loves Math IV
ZOJ 5340 - The Sum of Unitary Totient（常规积性函数求和，数据组数较多，只可分段打表）
SPOJ DIVCNT3 - Counting Divisors (cube)（常规积性函数求和，注意代码长度限制，不可打表）
51Nod 1575 - Gcd and Lcm（常规积性函数求和，可分段打表）
51Nod 1847 - 奇怪的数学题（非常规积性函数求和，综合题，可分段打表）