題目大意

求 $\sum_{i = 1}^{n} \sum_{j = 1}^{m} \mu(\lcm(i, j))$ 。
$ 1 \le n, m \le 10^6 $ 。

分析

不妨設 $ n \le m$ 。

$ \mu(\lcm(i, j)) = \mu(i) \mu(j) \mu(\gcd(i, j)) $

令 $S = \sum_{i = 1}^{n} \sum_{j = 1}^{m} \mu(\lcm(i, j))$

\begin{aligned}
S &= \sum_{i = 1}^{n} \sum_{j = 1}^{m} \mu(i) \mu(j) \mu(\gcd(i, j)) \\
&= \sum_{d = 1}^{n} \mu(d) \sum_{i = 1}^{n} \sum_{j = 1}^{m} \mu(i) \mu(j) [\gcd(i, j) = d] \\
&= \sum_{d = 1}^{n} \mu(d) \sum_{i = 1}^{n/d} \sum_{j = 1}^{m/d} \mu(id) \mu(jd) \color{red}{ [\gcd(i, j) = 1] } \\
&= \sum_{d = 1}^{n} \mu(d) \sum_{i = 1}^{n/d} \sum_{j = 1}^{m/d} \mu(id) \mu(jd) \color{red}{ \sum_{k \mid \gcd(i, j)} \mu(k) } \\
&= \sum_{d = 1}^{n} \mu(d) \sum_{i = 1}^{n/d} \sum_{j = 1}^{m/d} \mu(id) \mu(jd) \color{red}{ \sum_{k \mid i, k \mid{j}} \mu(k) } \\
&= \sum_{d = 1}^{n} \mu(d) \sum_{k = 1}^{n / d} \mu(k) \sum_{i = 1}^{n/d} \sum_{j = 1}^{m/d} \mu(id) \mu(jd) \sum_{k \mid i, k \mid{j}} 1 \\
&= \sum_{d = 1}^{n} \mu(d) \sum_{k = 1}^{n / d} \mu(k) \sum_{i = 1}^{n/(dk)} \sum_{j = 1}^{m/(dk)} \mu(idk) \mu(jdk)
\end{aligned}

上述紅色部分即用莫比烏斯函數的性質 $\sum_{d\mid n} \mu(d) = [n = 1]$ 進行化簡的套路。

固定 $dk$（即令 $t = dk$），有

\begin{aligned}
S = \sum_{t = 1}^{n} \color{blue}{ \sum_{d \mid t} \mu(d) \mu(t / d) } \sum_{i = 1}^{n/t} \mu(it) \sum_{j = 1}^{m/t} \mu(jt)
\end{aligned}

$\sum_{d \mid t} \mu(d) \mu(t / d)$ 即 $(\mu * \mu) (t)$ 。

預處理

對于 $t$ 從 $1$ 到 $n$，求

• $\mu(t)$，用線性篩，復雜度 $O(n)$ 。
• $\sum_{d \mid i} \mu(d) \mu(i / d)$，復雜度 $O(n \log n)$ 。
• $\sum_{i = 1}^{n/t} \mu(it)$ 和 $ \sum_{j = 1}^{m/t} \mu(jt) $，復雜度 $O(m \log m)$ 。

轉載于:https://www.cnblogs.com/Patt/p/11490010.html

總結

以上是生活随笔為你收集整理的HDU 6175 算术的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。