总结一些有关莫比乌斯函数的应用以及一些数论方面的东西。
1. \(k|\gcd(x,y) \Leftrightarrow k|x \text{ and } k|y\)
这个 trick 比较显然，不过还是小小的证明一下。
因为 \(\gcd(x,y)\) 同时整除 \(x,y\)，所以满足左边一定满足右边。因为 \(\gcd(x,y)\) 是最大公因数，如果满足右边而不满足左边，那么一定存在一个 \(z\) 使得 \(\gcd(x,y)\times z\) 也是 \(x,y\) 的公因数，和最大公因数的定义矛盾。
因此，若有式子 \(\sum_{x=1}^n\sum_{y=1}^m\sum_{k|\gcd(x,y)}\mu(k)\)，后面的 \(k|\gcd(x,y)\) 就可以换成 \(k|x\text{ and }k|y\)，这样的话就可以交换求和符号把 \(k\) 提前了。
这个 trick 对于 \(\gcd\) 内有多个元素同样有效。
2. 若要计算 \(f(\gcd(x,y))\)，可以设 \(f(n)=\sum_{d|n}g(d)\) 来化简式子。
举个简单的例子，我们需要计算 \(\sum_{x=1}^n\sum_{y=1}^m\gcd(i,j)\)。
当然，这个并不典型，而且大多数人都会枚举 \(\gcd\) 做，不过我们现在使用当前的这个 trick 来解决这个问题。
我们设 \(f(n)=n\)，且 \(f(n)=\sum_{d|n}g(d)\)，那么原式就变成了 \(\sum_{x=1}^n\sum_{y=1}^m\sum_{d|\gcd(x,y)}g(d)\) 。然后就可以通过 trick 1 交换求和符号把 \(d\) 提前了。而根据莫比乌斯反演，我们可以知道 \(g(n)=\sum_{d|n}f(d)\mu(\frac{n}{d})\)（在该例题中恰好是 \(\mu*id=\varphi\)），那么也可以很快地计算出 \(g\)。这样就通过这个 trick 达到了简化式子的效果，而且在一些情况下比直接枚举 \(\gcd\) 再把式子化来化去简单。
同样的，这个 trick 对于 \(\gcd\) 内有多个元素同样有效。
3. 设 \(d(x)\) 为 \(x\) 的因子个数，那么 \(d(n\times m)=\sum_{x|n}\sum_{y|m}[\gcd(x,y)=1]\)。
可以发现，把所有合法的 \(x,y\) 拿出来，然后列出所有的 \(x\times \frac{m}{y}\)，这就是所有 \(n\times m\) 的因子。
肯定不能感性的就这么理解，考虑严谨一点点的证明。
先证明每个因子一定存在一种方式可以得到。
我们假设 \(n=\prod p_i^{a_i},m=\prod p_i^{b_i}\)，设某个 \(n\times m\) 的因子 \(d=\prod p_i^{c_i}\) 。对于 \(d\) 的某个质因子及其次幂 \(p_i^{c_i}\)，以及对应的 \(n,m\) 的质因子及其次幂 \(p_i^{a_i},p_i^{b_i}\)。分两种情况讨论。
- 若 \(c_i\leq b_i\)，则使 \(x\) 中 \(p_i\) 的次幂为 \(0\)，\(y\) 中 \(p_i\) 的次幂为 \(b_i-c_i\)。这样在 \(x\times \frac{m}{y}\) 中 \(p_i\) 的次幂为 \((0)+(b_i-(b_i-c_i))=c_i\)，且 \(p_i\) 在 \(\gcd\) 中的贡献为 \(p_i^{\min(0,b_i-c_i)=0}=1\)。
- 若 \(c_i>b_i\)，又因为 \(c_i\leq a_i+b_i\)，所以 \(c_i-b_i\leq a_i\)，则使 \(x\) 中 \(p_i\) 的次幂为 \(c_i-b_i\)，\(y\) 中 \(p_i\) 的次幂为 \(0\)。这样在 \(x\times \frac{m}{y}\) 中 \(p_i\) 的次幂为 \((c_i-b_i)+(b_i-0)=c_i\)。且 \(p_i\) 在 \(\gcd\) 中的贡献为 \(p_i^{\min(c_i-b_i,0)=0}=1\)
这样的话，对于因子 \(d\) 的每个 \(p_i\) 都这么构造一下即可。
再证明每个因子只能由这一种方式得到。
根据上一部分的证明，不能发现这个性质其实是显然的。不过还是简要说一下。
对于上文的情况 1，若要使 \(p_i\) 在 \(\gcd\) 中的贡献为 \(1\)，而 \(x\) 中 \(p_i\) 的次幂 \(\not=0\)，那么 \(y\) 中 \(p_i\) 的次幂必须为 \(0\)，而此时 \(x\times \frac{m}{y}\) 中 \(p_i\) 的次幂最小为 \((1)+(b_i-0)=b_i+1> b_i\geq c_i\)，故构造不出 \(c_i\)。
对于上文的情况 2，若要使 \(p_i\) 在 \(\gcd\) 中的贡献为 \(1\)，而 \(y\) 中 \(p_i\) 的次幂 \(\not=0\)，那么 \(x\) 中 \(p_i\) 的次幂必须为 \(0\)，而此时 \(x\times \frac{m}{y}\) 中 \(p_i\) 的次幂最大为 \((0)+(b_i-1)=b_i-1<b_i<c_i\)，故构造不出 \(c_i\)。
综上就可以证明这个 trick。
同样的，这个 trick 对于多个元素的乘积同样有效，即：
\(d(\prod a_i)=\sum_{b_1|a_1}\sum_{b_2|a_2}...[\gcd(b_1,b_2)=1][\gcd(b_1,b_3)=1][\gcd(b_2,b_3)=1]...\)。
4. 若求和式中出现枚举 \(x,y\) 且涉及到了 \(xy\) 时，大多数时候需要改变思路枚举 \(xy\)。
其实这个是一个十分普遍的小 trick。
还是用那个老到不能再老的例子举例，求 \(\sum_{i=1}^n\sum_{j=1}^n\gcd(i,j)\)。
我们来枚举 \(\gcd\)，然后变化一下就有 \(\sum_{d=1}^nd\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(i,j)=1]\) 。根据常识，就有 \(\sum_{d=1}^nd\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\mu(k)\lfloor\frac{n}{kd}\rfloor\lfloor\frac{n}{kd}\rfloor\)，直接这么做就是 \(n\log n\) 的，而且对于 \(n\) 很大或者是多组询问不太好优化。
我们发现求和式中出现了 \(d\)，也出现了 \(k\)，同时涉及到了 \(dk\)，那么考虑设 \(T=dk\)，我们来枚举 \(T\)，就有 \(\sum_{T=1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{n}{T}\rfloor\sum_{k|T}\mu(k)\frac{T}{k}\)。这样的话，有个求和变成了狄利克雷卷积，而一般来说卷出来的东西是积性函数。这样的话，前面的东西就可以用整数分块，而后面的东西可以线性筛预处理，或者使用亚线性筛直接求。这样大大加快了代码运行的时间。