P2303 [SDOI2012] Longge 的问题
\[\sum_{i=1}^{n} \gcd(i,n) \]\[= \sum_{d | n} \sum_{i=1}^{n} d [gcd(i,n) == d] \]\[= \sum_{d | n} d \sum_{i=1}^{n} [gcd(i,n) == d] \]\[= \sum_{d | n} d \sum_{i=1}^{\frac{n}{d}} [gcd(i,n) == 1] \]\[= \sum_{d | n} d \; \varphi (\frac{n}{d}) \]P1891 疯狂 LCM
\[\sum_{i = 1}^n \operatorname{lcm}(i, n) \]\[=\sum_{i = 1}^n \frac{i\times n}{\gcd(i,n)} \]\[=n \sum_{i = 1}^n \frac{i}{\gcd(i,n)} \]\[=n \frac{\sum_{i=1}^n i}{\sum_{i=1}^n \gcd(i,n)} \]考虑分母
\[\sum_{i=1}^n \gcd(i,n) = \]\[= \sum_{d | n} \sum_{i=1}^{n} d [gcd(i,n) == d] \]\[= \sum_{d | n} d \sum_{i=1}^{n} [gcd(i,n) == d] \]\[= \sum_{d | n} d \sum_{i=1}^{\frac{n}{d}} [gcd(i,n) == 1] \]\[= \sum_{d | n} d \; \varphi (\frac{n}{d}) \] 标签：frac,gcd,sum,varphi,数学,合集,式子 From： https://www.cnblogs.com/BorisDimitri/p/16930450.html