题解：UVA11255 Necklace
Mashu77
·
·
题解
直接化式子。
\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{\gcd(i,j)}
枚举 \gcd
\sum_{d=1}^{n}\sum_{i=1}^{n}\sum_{j=1}^{m}\frac{ij}{k}[\gcd(i,j)=d] \\\sum_{d=1}^{n}\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\frac{ijd^2}{d}[\gcd(i,j)=1]\\\sum_{d=1}^{n}d\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}ij[\gcd(i,j)=1]
将后部拎出来，设为
u
m
(
\lfloor \frac{n}{d} \rfloor,\lfloor \frac{m}{d} \rfloor
)$。可以整除分块。于是现在只需要求：
$$sum(n,m)=\sum_{i=1}^{n}\sum_{j=1}^{m}ij[\gcd(i,j)=1]$$
莫比乌斯函数：
$$\sum_{i=1}^{n}\sum_{j=1}^{m}ij\sum_{k|\gcd(i,j)}\mu(k)$$
$k$ 提到前面：
$$\sum_{k=1}^{n}\mu(k)\sum_{i=1}^{n}\sum_{j=1}^{m}ij[k|\gcd(i,j)]\\\sum_{k=1}^{n}\mu(k)k^2\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor}i\sum_{j=1}^{\lfloor \frac{m}{k} \rfloor}j$$
后部提出来，可以
$O
(
1
)
算：
g(n,m)=\sum_{i=1}^{n}i\sum_{j=1}^{m}j=\frac{n(n+1)}{2}\frac{m(m+1)}{2}
\sum_{k=1}^{n}\mu(k)k^2g(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{m}{k} \rfloor)
又可以整除分块。于是总时间复杂度
(
\sqrt
n
\sqrt n)=
O
(
n
)$。