「Note」欧拉反演

求$\sum_{i=1}^n\gcd(i,n)$
$$ \sum_{d|n}\varphi(d) = n\\ \rightarrow \sum_{i=1}^n\gcd(i,n) = \sum_{i=1}^n\sum_{d|\gcd(i,n)}\varphi(d)\\ $$

$$ =\sum_{i=1}^n\sum_{d|i}\sum_{d|n} \varphi(d) \\ $$ $$ =\sum_{d|n}\sum_{i=1}^n\sum_{d|i} \varphi(d) \\ $$ $$ =\sum_{d|n}\frac{n}{d}\varphi(d) $$

然后可以直接整除分块。