积性函数：
若函数 \(f(x)\) 满足：\(f(1)=1\) 且 \(∀x,y∈N_+,\gcd(x,y)=1\) 都有 \(f(xy)=f(x)f(y)\)，则称它为积性函数。
若函数 \(f(x)\) 满足：\(f(1)=1\) 且 \(∀x,y∈N_+\) 都有 \(f(xy)=f(x)f(y)\)，则称它为完全积性函数。
性质：若 \(f(x),g(x)\) 均为积性函数，那么则以下函数也为积性函数：
\[\begin{aligned} h(x)&=f(x^p)\\ h(x)&=f^p(x)\\ h(x)&=f(x)g(x)\\ h(x)&=∑_{d|x}f(d)g(\frac{x}{d}) \end{aligned} \]积性函数的例子：
- 单位函数：\(ε(n)=[n=i]\) （完全积性）
- 恒等函数：\(id_k(n)=n^k\)，通常地，我们将 \(id_1(n)\) 记作 \(id(n)\) 。（完全积性）
- 常数函数：\(1(n)=1\)（完全积性）
- 除数函数：\(σ_k(n)=∑_{d|n}d^k\) ，通常地，我们将 \(σ0(n)\) 记作 \(d(n)\) 或者 \(τ(n)\)，\(σ_1(n)\) 记作\(σ(n)\) 。
- 欧拉函数：\(φ(n)=∑^n_{i=1}[gcd(i,n)=1]\)
- 莫比乌斯函数：\(\mu(n)=\begin{cases}\begin{aligned}&1& &n = 1\\&0& &\exists \ d>1,d^2|n \\&(-1)^{\omega(n)} && \text{otherwise}\end{aligned}\end{cases}\)
迪利克雷卷积（Dirichlet卷积）
定义
卷积专指的是函数见乘法运算，迪利克雷卷积是其中一种。对于两个数论函数 \(f(x)\)
和 \(g(x)\)，将他们进行迪利克雷卷积，结果 \(h(x)\) 定义为：
可以简写成：
\[h=f*g \]性质 ：
- 交换律：\(f*g=g*f\)
- 结合律：\((f*g)*h=f*(g*h)\)
- 分配律：\((f+g)*h=f*h+g*h\)
- 等式的性质：\(f=g\) 的充要条件：\(f*h=g*h\)，其中 \(h(x)\) 满足 \(h(1)≠0\)。
单位元：单位函数 \(ε\) 是迪利克雷卷积运算中的单位元，即：对于任意函数 \(f\)，存在 \(ε*f=f\)。
逆元：对于任意一个满足 \(f(x)≠0\) 的数论函数，假设存在一个 \(g(x)\)，满足 \(g*f=ε\)，则称\(g(x)\) 是 \(f(x)\) 的逆元。并且有且仅有 \(1\) 个。
莫比乌斯反演
定义 \(μ\) 为莫比乌斯函数，定义：
\[μ= \begin{cases} \begin{aligned} &1 & &n = 1\\ &0 & &\text{n 含有平方因子}\\ &(-1)^k & & \text{k 为 n 本质不同质因子个数} \end{aligned} \end{cases} \]性质
\[∑_{d|n}μ(d)=\begin{cases}1 &n=1\\ 0 &n\ne 1 \end{cases} \]即：\(∑_{d|n}μ(d)=ε(n),μ*1=ε\)
\[[\gcd(i,j)=1]=∑_{d|\gcd(i,j)}μ(d) \]\(\text{Description}\)：
已知 \(F_{m} = \sum_{a_1=1}^{m} \sum_{a_2=1}^{m} \cdots \sum_{a_n=1}^{m} [\gcd(a_1,a_2,\cdots a_n)=1]\) ，求 \(\sum_{i=1}^{k} F_i\)，\(1\le k,n\le 2\times 10^6\)
\(\text{Solution}\)：
考虑：
\[\begin{aligned} S &= \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=1]\\ &= \sum_{i=1}^n \sum_{j=1}^m \sum_{d|\gcd(i,j)} \mu(d) \\ &= \sum_{i=1}^{n} \sum_{d|i} \mu(d) \times \lfloor \frac{m}{d} \rfloor\\ &= \sum_{d=1}^{n} \mu(d) \times \lfloor \frac{m}{d} \rfloor \times \lfloor \frac{n}{d} \rfloor \end{aligned} \]所以有
\[F_k = \sum_{d=1}^k \mu(d) \times {\lfloor \frac{k}{d} \rfloor} ^ n \]直接整除分块是 \(k \times \sqrt k \log n\) 的，注意到：
\[\lfloor \frac{k}{d} \rfloor \ne \lfloor \frac{k-1}{d} \rfloor \Leftrightarrow d | k \]我们发现 \(F_k\) 在每 \(d\) 个段都会发生变化，而在段内不变。考虑维护差分数组：
\[\begin{aligned} \Delta f &= \sum_{d|k}^k \mu(d) \times ({\lfloor \frac{k}{d} \rfloor}^n - {\lfloor \frac{k-1}{d} \rfloor}^n) \end{aligned} \]然后做完了，复杂度 \(O(n \times (\log n + \log k))\)
线性筛求 \(\mu(x)\)
int pi[N], Ip[N], mu[N], tot;
void get() {
mu[1] = 1;
for(int i = 2; i <= lim; ++i) {
if(!Ip[i]) {
pi[++tot] = i;
mu[i] = -1;
}
for(int j = 1; j <= tot; ++j) {
if(pi[j] * i > lim) break;
Ip[i * pi[j]] = 1;
if(i % pi[j] == 0) {
mu[i * pi[j]] = 0;
break;
}
mu[i * pi[j]] = -mu[i];
}
}
}