Description
\[ \sum_{i=1}^n\sum_{j=1}^m lcm(i,j), 1 \leq n,m \leq 10^7 \]
Solution
假设 \(n\leq m\) \[ \begin{aligned} \sum_{i=1}^n\sum_{j=1}^m lcm(i,j) &=\sum_{i=1}^n\sum_{j=1}^m\frac{ij}{(i,j)}\\ &=\sum_{g=1}^n\sum_{i=1}^{\frac{n}{g}}\sum_{i=1}^{\frac{m}{g}}ijg \left[\left(i,j\right)=1\right]\\ &=\sum_{g=1}^n\sum_{d=1}^{\frac{n}{g}}\sum_{i=1}^{\frac{n}{dg}}\sum_{j=1}^{\frac{m}{dg}}idjdg\mu(d)\\ &=\sum_{T=1}^nT\sum_{d\mid T}d\mu(d)\sum_{i=1}^{\frac{n}{T}}i\sum_{j=1}^{\frac{n}{T}}j \end{aligned} \]
只要能预处理出 \(G(T)=\sum_{d\mid T}d\mu(d)\) 即可。
如果有 \(T=\prod P_i^{x_i}\) 则 \(G(T)=1-P_1-P_2...+P_1P_2+P_1P_3...-P_1P_2P_3...\) 那么如果 \(P\mid T\) 则 \(G(PT)=G(P)\) 否则 \(G(PT)=G(T)-PG(T)\)
