题目大意
一句话题意：给定n,m,求$\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)(n,m<=10^7)$
-
-
题解
$ans=\sum_{i=1}^{n}\sum_{j=1}^{m}lcm(i,j)=\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{i\times j}{gcd(i,j)}$
令$d=gcd(i,j)$，$F(x,y)=\sum_{1<=i<=x,1<=j<=y,gcd(i,j)=1}^{ }i \times j$
然后我们枚举$d$，则有$ans=\sum_{d=1}^{min(n,m)}\frac{d^2 \times F(\left [ \frac{n}{d} \right ],\left [ \frac{m}{d} \right ])}{d}=\sum_{d=1}^{min(n,m)}d\times F(\left [ \frac{n}{d} \right ],\left [ \frac{m}{d} \right ])$
令$Sum(x,y)=\sum_{i=1}^{x}\sum_{j=1}^{y}i \times j=\frac{x(x-1)}{2}\times\frac{y(y-1)}{2}$
显然$Sum(x,y)=\sum_{i=1}^{min(x,y)}i^2 \times F(\left [ \frac{x}{i} \right ],\left [ \frac{y}{i} \right ])$
通过莫比乌斯反演可得$F(x,y)=\sum_{i=1}^{min(x,y)}i^2\times \mu(i)\times Sum(\left [ \frac{x}{i} \right ],\left [ \frac{y}{i} \right ])$
这两个式子都可以进行$O(\sqrt n)$的计算，所以总的时间复杂度是$O(n)$
参考代码
|
|