Luogu1829Crash的数字表格


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)\)


文章作者: ffacs
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 ffacs !
  目录