![[洛谷 P1891] 疯狂 LCM (欧拉函数 莫比乌斯反演)](/uploads/reation/bcimg13.png)
[洛谷 P1891] 疯狂 LCM (欧拉函数 莫比乌斯反演)
题意：求∑i=1nlcm(i,n)\sum_{i=1} ^{n} \text{lcm}(i,n)i=1∑nlcm(i,n)分析：法一：拆一下 lcm(i,n)=i⋅ngcd(i,n)\text{lcm}(i,n) = \dfrac{i \cdot n}{\gcd{(i,n)}}lcm(i,n)=gcd(i,n)i⋅n 变为：∑i=1ni⋅ngcd(i,n)\sum_{i=1} ^{n} \frac{i \cdot n}{\gcd{(i,n)}}i=1∑ngcd(i,n)i⋅n枚举
