狄利克雷卷积
对于两个数论函数
f 和
g，那么定义其狄利克雷卷积结果
h 为
h(x)=∑d∣xf(d)g(dx)=∑ab=xf(a)g(b)，记为
h=f∗g狄利克雷这么定义是有他的道理，我们发现这个运算满足交换律、结合律、分配律，而且两个积性函数的狄利克雷卷积还是积性函数，均可推式子求证
还是定义：
- 1: f(x)=1
- ε: 单位元，对于任意数论函数 f，有 f∗ε=f，具体内容是 ε(x)=[x=1]
- idk: 幂函数，idk(x)=xk，k=1 时可省略 k
- μ: 莫比乌斯函数，具体是
\mu(x) &=
\begin{cases}
1 & \text{if } x =0 \\
0 & \text{if } \exists \text{ }p\in P, p^2\mid x \\
(-1)^k & \text{if }x=\prod_{i=1}^k p_i \land\forall p_i,p_i\in P\land \forall i\neq j, p_i\neq p_j
\end{cases}
\end{align*}$$
5. $\varphi$: 欧拉函数，$\varphi(x)=\sum_{i=1}^x[\gcd(i,x)=1]=x\prod_{p\in P,p|x}\frac{p-1}{p}$
那么我们就可以发现：
1. $\varepsilon=\mu * 1$
2. $\varphi=\mu * id$
3. $id=\varphi * 1$
还有很多别的常用卷积式，不过已经够了
# 杜教筛
定义大写字母为原函数的前缀和，例 $F(x)=\sum_{i=1}^x f(x)$
我们需要快速求解 $F(x)$，直接做很明显是劣的，于是便有了快速求解的方法——杜教筛
对于任意一个数论函数 $g$，令 $h=f * g$，则有：
$$\begin{aligned}
H(n)&=\sum_{i=1}^n\sum_{d\mid i}g(d)f(\frac{i}{d})\\
&=\sum_{i=1}^n\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}g(i)f(j)\\
&=\sum_{i=1}^ng(i)\sum_{j=1}^{\lfloor\frac{n}{i}\rfloor}f(j)\\
&=\sum_{i=1}^ng(i)F(\lfloor\frac{n}{i}\rfloor)
\end{aligned}$$
进而便有：
$$g(1)F(n)=H(n)-\sum_{i=2}^ng(i)F(\lfloor\frac{n}{i}\rfloor)$$
于是如果 $H(n)$ 和 $G(n)$ 是好求的，便可以进行递归+根号分治求解
然而复杂度正确吗？首先可以预处理 $H(n)$，再线性筛掉前 $m$ 个 $F(n)$，注意到这是 $O(m)$ 的
然后再进行递归，设求 $F(n)$ 的复杂度是 $T(n)$ 的，则
$$\begin{aligned}
T(n)&=O(m)+\sum_{k=2}^n [\lfloor\frac{n}{k}\rfloor>m]T(\lfloor\frac{n}{k}\rfloor)\\
&=O(m)+\sum_{k=1}^{\lfloor\frac{n}{m}\rfloor}O(\sqrt\frac{n}{k})\\
&=O(m+\int_0^{\frac{n}{m}}\sqrt{\frac{n}{x}}\mathrm{d}x)\\
&=O(m+\frac{n}{\sqrt{m}})
\end{aligned}$$
于是使用均值不等式，当 $m=n^{\frac{2}{3}}$ 时，$T(n)=O(n^{\frac{2}{3}})$
模板代码：
```cpp
int F(int n) {
if (n <= m) return init[n]; // 预处理
if (mp[n]) return mp[n]; // 记忆化
int ans = H(n);
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l); // 根号分治
ans -= (G(r) - G(l - 1)) * F(n / l);
}
return mp[n] = ans / g1;
}
```
# [【模板】杜教筛](https://www.luogu.com.cn/problem/P4213)
> 求 $\sum_{i=1}^n\mu(n),\sum_{i=1}^n\varphi(n)$
根据 $\mu * 1=\varepsilon,\varphi * 1=id$，然后套用模板代码求解即可
code:
```cpp
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std;
const int maxn = 1e6 + 10, mod = 998244353;
vector<int> pr;
map<int, int> mphi, mmu;
int m, iphi[maxn], imu[maxn], ntp[maxn];
int mu(int n) { // mu * 1 = epsilon
if (n <= m) return imu[n];
if (mmu[n]) return mmu[n];
int ans = 1;
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ans -= (r - l + 1) * mu(n / l);
}
return mmu[n] = ans;
}
int phi(int n) { // phi * 1 = id
if (n <= m) return iphi[n];
if (mphi[n]) return mphi[n];
int ans = n * (n + 1) / 2;
for (int l = 2, r; l <= n; l = r + 1) {
r = n / (n / l);
ans -= (r - l + 1) * phi(n / l);
}
return mphi[n] = ans;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
m = 1000000;
ntp[1] = iphi[1] = imu[1] = 1;
for (int i = 2; i <= m; i++) {
if (!ntp[i]) pr.push_back(i), iphi[i] = i - 1, imu[i] = -1;
for (int p : pr) {
if (i * p > m) break;
ntp[i * p] = 1;
if (i % p == 0) {
iphi[i * p] = iphi[i] * p;
break;
}
iphi[i * p] = iphi[i] * (p - 1);
imu[i * p] = -imu[i];
}
}
for (int i = 1; i <= m; i++) imu[i] += imu[i - 1], iphi[i] += iphi[i - 1];
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
cout << phi(n) << " " << mu(n) << endl;
}
return 0;
}
```
---
似乎能水一篇题解... 
Pollard-Rho