前置知识
\(1.\) 艾佛森括号：
\([P]=\begin{cases}1 & \mathtt{(if\ P\ is \ true)}\\0 & \mathtt{(otherwise)}\end{cases}\)
\(2.\) \(a\mid b\) 表示 \(a\) 是 \(b\) 的因子
\(3.\) 整除分块：\(\displaystyle\sum_{i=1}^n\lfloor\dfrac{N}{i}\rfloor\)
\(4.\) \(p\) 没有特殊说明时表示质数
\(5.\) \(\mathbb{P}\) 表示质数集，\(\mathbb{Z}\) 表示整数集。
\(6.\) 常见的函数：
- 常函数：\(1(x)=1\)
- 单位元函数：\(\epsilon(x)=[x=1]\)
- 恒等函数：\(Id_k(x)=x^k\)
- 因子函数：\(d(x)=\displaystyle\sum_{i\mid x}1\)
- 因子和函数：\(\sigma(x)_k=\displaystyle\sum_{i\mid x}i^k\)
- 欧拉函数：\(\varphi(x)=\displaystyle\sum_{i=1}^x[\gcd(i,x)=1]\)
函数
数论函数
数论函数指一类定义域是正整数，值域是一个数集的函数。有：
- \((f+g)(x)=f(x)+g(x)\)
- \((x*f)(n)=x*f(n)\)
积性函数
当数论函数 \(f\) 对于 \(\gcd(n,m)=1\) 有：
\[f(nm)=f(n)f(m)\]
则数论函数 \(f\) 为积性函数。
例如：\(d(x),\varphi(x)\)
完全积性函数
当积性函数 \(f\) 对于 \(\gcd(n,m)\not=1\) 仍有：
\[f(nm)=f(n)f(m)\]
则积性函数 \(f\) 为完全积性函数。
例如：\(\epsilon(x),id_k(x)\)
积性函数的实现
那么，积性函数像下面的 \(\varphi,\mu\) 都是非常有用的东西，当然还有更多的积性函数，那么我们该如何去线性求出积性函数呢。
我们需要通过想欧拉筛筛质数的方式来快速筛出积性函数。
比如我们现在要筛积性函数 \(f\)，那么我们就需要快速的得到它的 \(f(1),f(p),f(p^t)\)。
我们需要先对每一个 \(i\) 进行唯一分解 \(\displaystyle\prod_{i=1}^kp_i^{t_i}\)。
<ul>当 \(p |
