[BZOJ 4173]数学

一、题目

二 、解法

又到了欢乐推式子时间，先推那个判断式（本文所有除法均为整除）：
$m\%k+n\%k\geq k$m%k+n%k≥k$m-\frac{m}{k}k+n-\frac{n}{k}k\geq k$m−km​k+n−kn​k≥k$\frac{n+m}{k}-\frac{m}{k}-\frac{n}{k}\geq1$kn+m​−km​−kn​≥1由于$0\leq\frac{n+m}{k}-\frac{m}{k}-\frac{n}{k}\leq1$0≤kn+m​−km​−kn​≤1，所以可以直接把上面的值当成判断式来用，也就是说，我们现在要求这东西：
$\phi(n)\phi(m)\sum_{k=1}^{n+m}(\frac{n+m}{k}-\frac{m}{k}-\frac{n}{k})\phi(k)$ϕ(n)ϕ(m)k=1∑n+m​(kn+m​−km​−kn​)ϕ(k)可以把上面的问题分解成三个差不多的子问题，我们继续推式子：
$\sum_{k=1}^n\frac{n}{k}\phi(k)=\sum_{k=1}^n\sum_{d|k}\phi(k)=\sum_{k=1}^n k$k=1∑n​kn​ϕ(k)=k=1∑n​d∣k∑​ϕ(k)=k=1∑n​k推出来了一个优美的求和，所以原式$=nm$=nm（三个求和再推下就完了），最后的答案为$\phi(n)\phi(m)nm$ϕ(n)ϕ(m)nm。本题要写高精，都推到这一步了，代码就不给了吧qwq。