懵逼钨丝常用套路公式

1. $[n=1]=\sum_{d|n}\mu_d $

   可以把一个“判一”的式子化成可以计算的函数

   $[\gcd(a,b)=1]=\sum_{d|\gcd(a,b)}\mu_d $

2. $n=\sum_{d|n}\varphi_d $

   把一个数化到枚举范围里面去

   $\gcd(a,b)=\sum_{d|\gcd(a,b)}\varphi_d $

3. 重排变换

   $\sum_{i=1}^n\sum_{d|\gcd(i,n)}f_d=\sum_{d|n}f_d\lfloor\frac{n}{d}\rfloor $

4. 混合重排变换

   $\sum_{i=1}^n\sum_{d|\gcd(i,m)}f_d=\sum_{d|m}f_d\lfloor\frac{n}{d}\rfloor $

5. 扩展混合重排变换

   $\sum_{i=1}^n\sum_{d|\gcd(i,m)}f_dg_i=\sum_{d|m}f_d\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}g_{id} $

6. 扩展变换

   $\sum_{i=1}^n[d|i]f_i=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}f_{id}$

7. 收缩变换

   $\sum_{i=1}^n\sum_{d|i}f_d=\sum_{i=1}^n\sum_{d=1}^{\lfloor\frac{n}{i}\rfloor}f_d $

8. 杜教筛变换

9. 约数个数变换

   $d(x)=d_{nm}=\sum_{i|n}\sum_{j|m}[\gcd(i,j)=1] $

   x的约数个数