中间结论

$$
f_n = \sum_{i=0}^n (-1)^i {n \choose i} g_i
\Leftrightarrow
g_n = \sum_{i=0}^n (-1)^i {n \choose i} f_i
$$

$$
f_n = \sum_{i=0}^n {n \choose i} g_i
\Leftrightarrow
g_n = \sum_{i=0}^n (-1)^{n-i} {n \choose i} f_i
$$

杜教筛

$$
g(1)\sum_{i=1}^nf(i)=\sum_{i=1}^{n}(f*g)(i)-\sum_{d=2}^{n}g(d) \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i)
$$

数论变换

$$
\begin{aligned}
&e(n)=[n=1]
\&id(n)=n
\&I(n)=1
\&d(n)=\sum_{x|n}1 （就是因子个数）
\&σ(n)=\sum_{x|n}x (就是因子和)
\&\mu(n) 莫比乌斯函数
\&\phi(n) 欧拉函数
\&I\ast I=d
\&I\ast id=σ
\&I\ast \phi=id
\&I\ast \mu=e
\end{aligned}
$$

自变量互质的前缀和函数分析

$$
\begin{aligned}
&\sum_{i=1}^n{f(i)[gcd(i,j)=1]}=\sum_{d|j}{\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f(i*d)}\
&\sum_{i=1}^n{[gcd(i,j)=1]}=\sum_{d|j}{\mu(d)\lfloor\frac{n}{d}\rfloor}\
&\sum_{i=1}^n{[gcd(i,n)=1]}=\phi(n)\
&\sum_{i=1}^n{i[gcd(i,j)=1]}=\sum_{d|j}{\mu(d)d\frac{\lfloor\frac{n}{d}\rfloor(\lfloor\frac{n}{d}\rfloor+1)}{2}}\
&\sum_{i=1}^n{i[gcd(i,n)=1]}=\frac{n}{2}(\phi(n)+e(n))\
&\sum_{i=1}^n\sum_{j=1}^nij[gcd(i,j)=1]=\sum_{j=1}^nj^2\phi(j)\
\end{aligned}
$$