Contents
形式与套路式
划重点！一切莫比乌斯反演题推柿子都等价于以下套路!
\begin{aligned}
\left[gcd(i,j)=1\right]&\iff\sum_{d\mid gcd(i,j)}\mu(d)\cr
\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)]&\iff\sum_{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\mu(d)\cr
\sum_{i=1}^{n}[gcd(i,m)]&\iff\sum_{d|m}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\mu(d)
\end{aligned}
形式一：
设有函数f(x)与F(x)，则有：
F(n)=\sum_{d|n}f(d)\iff f(n)=\sum_{d|n}\mu(d)F\left(\frac{n}{d}\right)
形式二：
设有函数 f(x) 与 F(x)，则有：
F(n)=\sum_{n|d}f(d)\iff f(n)=\sum_{n|d}\mu\left(\frac{d}{n}\right)F(d)
重要结论
结论一：
\sum_{i=1}^{n}[gcd(i,n)=1]\cdot i=\frac{n\cdot\varphi(n)}{2}
感性理解：gcd(i,n)=gcd(n-i,n)，因此与 n 互质的数总是成对出现且每对的和为 n .
注意：做题时要特判 n=1 时上式为 1 .
也可用上面的套路式化简出（略）
结论二：
设 d(n) 为 n 的约数个数函数：
d(i\cdot j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]
结论三：
\begin{aligned}
f(n)&=\sum_{i=1}^n\sum_{j=1}^n ij [\gcd(i,j)=1]\cr
&=\left(\sum_{i=1}^n\sum_{j=1}^{i-1} ij [\gcd(i,j)=1]\right)+\left(\sum_{j=1}^n\sum_{i=1}^{j-1} ij [\gcd(i,j)=1]\right)+1\cr
&=2\left(\sum_{i=1}^n\sum_{j=1}^{i-1} ij[\gcd(i,j)=1]\right)+1\cr
&=2\left(\sum_{i=1}^n i\sum_{j=1}^{i-1} j[\gcd(i,j)=1]\right)+1\cr
&=2\left(\sum_{i=1}^n i\left(\frac{i\cdot \varphi(i)-[i=1]}{2} \right)\right)+1\cr
&=\sum_{i=1}^{n}i^2\varphi(i)
\end{aligned}
简单应用
例一：
\begin{aligned}
&\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)\cr
&=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i j}{gcd(i,j)}\cr
&=\sum_{d}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\cdot\frac{i j}{d}\cr
&=\sum_{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i,j)=1]\cdot i\cdot j\cdot d\cr\cr
\end{aligned}
设：
\begin{aligned}
sum(n,m)&=\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=1]\cdot i\cdot j\cr
&=\sum_{d}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\mu(d)\cdot d^2\cdot i\cdot j\cr
&=\sum_{d}d^2\cdot \mu(d)\cdot g(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)
\end{aligned}
其中：
g(n,m)=\frac{n(n+1)}{2}\cdot\frac{m(m+1)}{2}
\therefore 原式
=\sum_{d}d\cdot sum(\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor)
运用两次整除分块即可。
例二：
\begin{aligned}
&\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]\cr
&=\sum_{p}\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=p]\cr
&=\sum_{p}\sum_{d}\mu(d)\cdot \left\lfloor\frac{n}{pd}\right\rfloor\cdot \left\lfloor\frac{m}{pd}\right\rfloor\cr
\end{aligned}
枚举 pd，设 pd=t：
\begin{aligned}
&=\sum_{t}\left\lfloor\frac{n}{t}\right\rfloor\cdot \left\lfloor\frac{m}{t}\right\rfloor\sum_{p|t,p\in prime}\mu\left(\frac{t}{p}\right)
\end{aligned}
其中第一个求和可以整除分块，第二个求和可以预处理：
对于每一个质数 p，枚举其倍数 kp，sum(kp) += \mu(k)
高级技巧
线性筛任意积性函数
想要线性筛一个积性函数 f(n)，我们需要知道以下三个条件：
- $f(1)$
- $f(p),\ p\in prime$
- $f(p^k),\ p\in prime$
具体思路是，考虑筛的过程中，i ∗ prime[j] 会被 i 乘上 prime[j] 给筛掉。若将 i 唯一分解得到 p_1^{a_1}p_2^{a_2}\cdots p_k{a_k}，则一定有 prime[j] <= p1，因为当 prime[j] = p1 的时候就break掉了。
- 若
prime[j] < p1，则prime[j]与i互质，可以直接f[i* prime[j]] = f[i] ∗ f[prime[j]] -
若
prime[j] = p1，这时就需要对i记录一个low[i]，表示i中最小值因子的指数次幂，即 low_i = p_1^{a_1}（就是在唯一分解中的那个 p_1^{a_1}）。
– 如果使用 i 除掉 low[i] 那么结果中的最小质因子一定大于 p1，而又因为 prime[j] = p1，从而可知 gcd(i/low[i], lowi∗prime[j]) = 1。那么就可以 f[i∗prime[j]] = f[i/low[i]] ∗ f[low[i]*prime[j]]。
– 注意当 low[i] = i时表示这个数是一个质数的若干次幂，这个时候就需要用到上方的特殊定义。
伪代码：
int prime[N], num[N], f[N], low[N], tot;
void getf() {
low[1] = 1; f[1] = 1处的点值;
for (int i = 2; i < N; i++) {
if (!num[i]) {
prime[++tot] = i;
f[i] = 质数处的点值;
}
for (int j = 1, x; j <= tot && (x = i * prime[j]) < N; j++) {
num[x] = 1;
if (i % prime[j]) {
f[x] = f[i] * f[prime[j]];
low[x] = prime[j];
}
else {
low[x] = low[i] * prime[j];
if (low[i] == i) {
f[x] = 质数的k次方处点值;
}
else {
f[x] = f[i / low[i]] * f[low[i] * prime[j]];
}
break;
}
}
}
}
筛形如狄利克雷卷积的非积性函数
常规方法：复杂度 O(nlog_n)
h(x)=(f * g)(x)
for (int i = 1; i < N; i++) {
for (int j = 1; i * j < N; j++) {
(h[i * j] += f[i] * g[j]) %= P;
}
}
其中一个是莫比乌斯函数：复杂度 O(nloglog_n)
g(x)=f(x) * \mu(x)
考虑dp，设：
g(i,n)=\sum_{d|n,d只包含前i种质因子}\mu(d)f\left(\frac{n}{d}\right)
则：
g(i, n)=
\begin{cases}
g(i-1,n),&p_i\not | n;\cr g(i-1,n)-g\left(i-1,\frac{n}{p_i}\right),&p_i\ \ |n
\end{cases}
for (int i = 1; i < N; i++) {
g[i] = f[i];
}
for (int i = 1; i <= tot; i++) { // tot 为 n 以内筛出的质数个数
for (int j = (N - 1) / prime[i]; j; j--) {
(g[j * prime[i]] += P - g[j]) %= P;
}
}