集合统计（拆mod关系式 + 欧拉函数）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/142521016

http://noip.ybtoj.com.cn/contest/802/problem/6

对于： $n\bmod k+m\bmod k\ge k$ ，我们可以先把 $\bmod$ 拆掉：

$n-\lfloor \dfrac n k\rfloor\times k+m-\lfloor \dfrac m k\rfloor\times k\ge k$

两边同时除 $k$ ：

$\lfloor \dfrac {n+m} k\rfloor-\lfloor \dfrac n k\rfloor-\lfloor \dfrac m k\rfloor\ge 1$

发现式子成立时恰好取等：

$\lfloor \dfrac {n+m} k\rfloor-\lfloor \dfrac n k\rfloor-\lfloor \dfrac m k\rfloor= 1$

这个形式就非常好看，代回原式后就是套路了

$$\sum_{k=1}^{n+m}\varphi(k)\left( \lfloor \dfrac {n+m} k\rfloor-\lfloor \dfrac n k\rfloor-\lfloor \dfrac m k\rfloor\right)$$

$$\sum_{k=1}^{n+m}\varphi(k)\lfloor \dfrac {n+m} k\rfloor-\sum_{k=1}^{n}\varphi(k)\lfloor \dfrac n k\rfloor-\sum_{k=1}^{m}\varphi(k)\lfloor \dfrac m k\rfloor$$

令 $f(x)=\sum_{k=1}^{x}\varphi(k)\lfloor \dfrac {x} k\rfloor$ ，则原式为 $f(n+m)-f(n)-f(m)$

化简 $f(x)$ ，这是个经典问题。对于 $\varphi(k)$ 的贡献为它有多少个倍数在 $x$ 以内，因此我们枚举这个倍数：

$$f(x)=\sum_{i=1}^x\sum_{i|k}\varphi(k)=\sum_{i=1}^xi=\dfrac {x(x-1)}2$$

因此原式为 $\dfrac{(n+m)(n+m-1)-n(n-1)-m(m-1)}2=nm$

答案为 $\varphi(n)\varphi(m)nm$