P1829 [国家集训队]Crash的数字表格（莫比乌斯反演） P1829 [国家集训队]Crash的数字表格（莫比乌斯反演）
题目描述
求
[largesum_{i=1}^nsum_{j=1}^mlcm(i, j)
]
数据范围
(n,mleq 10^7)
解题思路
设 (n le m)
[largesum_{i=1}^nsum_{j=1}^mlcm(i, j)\
large=sum_{i=1}^nsum_{j=1}^m ij*gcd(i,j)^{-1}\
large=sum_{d=1}^ndsum_{i=1}^{frac nd}isum_{j=1}^{frac md} j[gcd(i,j)=1]\
large=sum_{d=1}^ndsum_{k=1}^{frac n{d}}mu(k)*k^2sum_{i=1}^{frac n{kd}}isum_{j=1}^{frac m{kd}} j\
large=sum_{d=1}^nd*Sum(frac nd,frac md)\
large Sum(n, m) = sum_{i=1}^nmu(i)*i^2sum_{j=1}^{frac ni}sum_{k=1}^{frac mi}ij
]
两个整除分块即可，时间复杂度 (Theta(n))