前置知识
积性函数
如果函数\(f(x)\)满足\(\forall x,y\in N_+,\gcd(x,y)=1,f(xy)=f(x)f(y)\)，则函数\(f(x)\)为积性函数
如果函数\(f(x)\)满足\(\forall x,y\in N_+,f(xy)=f(x)f(y)\)，则函数\(f(x)\)为完全积性函数
Dirichlet 卷积
令\(h(n)=\sum_{d|n}f(d)g(\frac{n}{d})\)，则称函数\(h\)是函数\(f\)和\(g\)的 Dirichlet 卷积。
Dirichlet 卷积满足交换律和结合律
两个积性函数的 Dirichlet 卷积也是积性函数
常见的 Dirichlet 卷积：
\[\mu * Id= \varphi\\
\varphi * I=Id\\
\mu * I=\epsilon
\]
点乘
定义点乘为：\((A \cdot B)(n)=A(n)B(n)\)
当 \(C\) 为完全积性函数时，\((A\cdot C) * (B\cdot C)=(A * B)\cdot C\)
证明：
\[Ans=\sum_{d|n}A(d)C(d)B(\frac{n}{d})C(\frac{n}{d})\\
=\sum_{d|n}A(d)B(\frac{n}{d})C(d)C(\frac{n}{d})\\
\because C为完全积性函数\\
\therefore Ans=C(n)\sum_{d|n}A(d)B(\frac{n}{d})
\]
常见应用：
\[(\mu \cdot Id_k) * Id_k=(\mu \cdot Id_k)* (I \cdot Id_k)=(\mu * I)\cdot Id_k=\epsilon\\
(\varphi \cdot Id_k) * Id_k=(\varphi \cdot Id_k)* (I \cdot Id_k)=(\varphi * I)\cdot Id_k=Id_{k+1}\\
\]
杜教筛
杜教筛可以用来求函数前缀和
令目标函数为\(f(x),S(n)=\sum_{i=1}^nf(i)\)，构造两个函数\(g(x),h(x)\)使得\(h=f * g\)
且\(g,h\)的前缀和可以快速算出
\[\sum_{i=1}^nh(i)=\sum_{i=1}^n\sum_{d|i}f(d)g(\frac{n}{d})\\
=\sum_{d=1}^n g(d)\sum_{i=1}^\frac{n}{d}f(i)\\
=\sum_{d=1}^n g(d) S(\frac{n}{d})\\
\therefore S(n)=\frac{\sum_{i=1}^nh(i)-\sum_{d=2}^n g(d)S(\frac{n}{d})}{g(1)}
\]
递归处理，预处理到 \(S(n^{\frac{2}{3}})\)，时间复杂度为\(O(n^{\frac{2}{3}})\)
例子
一：
求\(S(n)=\sum_{i=1}^n \mu(i)\)
\[\because \mu * I = \epsilon\\
\therefore S(n)=1-\sum_{d=2}^n d\times S(\frac{n}{d})
\]
二：
求\(S(n)=\sum_{i=1}^n \varphi(i)\)
\[\because \varphi * I=Id\\
\therefore S(n)=\sum_{i=1}^n i-\sum_{d=2}^n S(\frac{n}{d})
\]
三：
求\(S(n)=\sum_{i=1}^n i\varphi(i)\)
\[\because (Id \cdot \varphi) * Id= Id_2\\
\therefore S(n)=\sum_{i=1}^n i^2-\sum_{d=2}^n d\times S(\frac n d)
\]
Min_25筛
Min_25筛用来求一类特殊积性函数的前缀和，时间复杂度为\(O(n^{1-\epsilon})\)或者\(O(\frac{n^\frac 3 4}{\log n})\)
要求：\(\forall p\in P,c\in N_+,f(p^c)\)可以快速求值
模板
\[令L(n)为n的最小质因子,p_i为第i个质数\\
\sum_{i=1}^n f(i)=\sum_{p\in P}f(p)+\sum_{d\notin P}f(d)\\
\because 不超过 n 的合数一定有一个不大于 \sqrt n的质因子\\
\therefore \sum_{i=1}^n f(i)=\sum_{p\in P}f(p)+\sum_{p\in P \le \sqrt n\&p^e\le n}f(p^e)(\sum_{d=2\&L(d)>p}^\frac{n}{p^e}f(d))\\
设计一个完全积性函数f'，且f'与f在质数处取值相同\\
令g(n,j)=\sum_{i=1}^n[i\in P||L(i)>p_j]f'(i),x为满足p_x\le \sqrt n 的最大值\\
则\sum_{p\in P}^nf(p)=g(n,x)\\
考虑递推，g(n,j-1)\to g(n,j)\\
p_j^2>n,没有多余贡献，g(n,j)=g(n,j-1)\\
p_j^2\le n 提出p_j,贡献为f'(p_j)(g(\frac{n}{p_j},j-1)-\sum_{i=1}^{j-1}f'(p_i))\\
g(\frac{n}{p_j},j-1)-\sum_{i=1}^{j-1}f'(p_i)是含有p_j的合数的贡献\\
考虑令S(n,j)为\sum_{L(i)>p_j}f(i)\\
则：S(n,j)=g(n,j)-\sum_{i=1}^jf(i)+\sum_{k>j\&p^e\le n}f(p_k^e)(S(\frac{n}{p_k^e},k)+[e>1])
\\
\\
答案就是S(n,0)+f(1)
\]
注意：第一维的下标始终是\(\frac{n}{x}\)，所以可以将空间复杂度压到\(O(\sqrt n)\)
Powerful Number筛
Powerful Number
若正整数\(x\)满足它所有质因子的幂次都大于一，则\(x\)是一个\(\text{Powerful Number}\)
性质：
任何一个\(\text{Powerful Number}\)都可以表示为\(a^2b^3\)
\([1,n]\)之间的\(\text{Powerful Number}\)有\(O(\sqrt n)\)个
证明：个数是
\[\int_{i=1}^{\sqrt n} \sqrt[3]{\frac{n}{x^2}}dx=O(\sqrt n)
\]
Powerful Number筛
要求\(\sum_{i=1}^nf(i)\)
构造积性函数\(g\)满足：
- \(g\)是积性函数
- \(g\)容易求前缀和(有可能与杜教筛,min_25筛有关)
- \(\forall p\in P,g(p)=f(p)\)
令\(h=f/g\)，这里是 Dirichlet 除法，即\(f= g * h\)
所以\(h\)也为积性函数\(h(1)\)
\[\forall p\in P,f(p)=g(1)h(p)+h(1)g(p)=h(p)+g(p)\\
\therefore h(p)=0\\
\sum_{i=1}^nf(i)=\sum_{i=1}^n\sum_{d|i}h(d)g(\frac{i}{d})\\
=\sum_{i=1}^n h(i)\sum_{d=1}^\frac{n}{i}g(i)
\]
因为\(h\)为积性函数，所以只有\(\text{Powerful Number}\)的\(h\)不为\(0\)
下一个问题是如何得到\(h(p^c)\)
- 1、通过\(f=h * g\)算出\(h\),\(h(p^c)=f(p^c)-\sum_{i=1}^c f(p^i)h(p^{c-i})\)
- 2、找到\(h(p^c),p,c\)的关系
然后\(dfs\)找到所有\(PN\)数就行了