[BOJ 32240] 비로소 서로소
https://www.acmicpc.net/problem/32240
Task
Compute:
\[ \sum_{i=1}^{N} \sum_{j=1}^{N} (i+j) [\gcd(i,j) = 1] \]
for given integer $N$.
Solution
Computing directly would take more than $O(N^2)$ time, which is too slow for large $N$. Instead, we transform the sum as follows:
\[ \begin{align*} & \sum_{i=1}^{N} \sum_{j=1}^{N} (i+j) [\gcd(i,j) = 1] \nl =& \sum_{i=1}^{N} \sum_{j=1}^{N} (i+j) \sum_{d | \gcd(i,j)} \mu(d) = \sum_{i=1}^{N} \sum_{j=1}^{N} (i+j) \sum_{d=1}^{\min(i,j)} \mu(d) [d | i] [d | j] \nl =& \sum_{d=1}^{N} \mu(d) \sum_{i=1}^{\lfloor N/d \rfloor} \sum_{j=1}^{\lfloor N/d \rfloor} (di + dj) = \sum_{d=1}^{N} d \mu(d) \sum_{i=1}^{\lfloor N/d \rfloor} \sum_{j=1}^{\lfloor N/d \rfloor} (i + j) \nl =& \sum_{d=1}^{N} d \mu(d) \left\lfloor \frac{N}{d} \right\rfloor^2 \left( \left\lfloor \frac{N}{d} \right\rfloor + 1 \right) \end{align*} \]
Computing this transformed sum takes $O(N \log \log N)$ time to precompute the Möbius function values and $O(N)$ time to compute the final sum. However, this is not enough for the given constraints.
Optimization
Let’s optimize the summation by grouping terms with the same value of $\left\lfloor \frac{N}{d} \right\rfloor$. Denote $d_0 = 1$ and $a_i = \left\lfloor \frac{N}{d_i} \right\rfloor$.
\[ d_{i+1} = \left\lfloor \frac{N}{a_i} \right\rfloor + 1 \]
Then, we can rewrite the sum as follows:
\[ \sum_{i:d_i \le N} \left( \sum_{j=d_i}^{d_{i+1}-1} d \mu(d) \right) a_i^2 (a_i + 1) \]
This reduces the number of terms in the summation to $O(\sqrt{N})$. Next, we have to efficiently compute the inner sum $\sum_{j=d_i}^{d_{i+1}-1} d \mu(d)$. Precomputing $\mu(d)$ naively takes $O(N \log \log N)$ time, which is still too slow. Instead, we can use the Mertens trick to compute the inner sum in $O\left(N^{2/3}\right)$ time. Let $f(n) = n \mu(n)$ and we should compute $S_f(n)$ quickly. We should find a function $g(n)$ such that $S_g(n)$ and $S_{f * g}(n)$ can be computed in almost $O(1)$ time. We can choose $g = \text{Id}$, so that $f * g = \varepsilon$. Then, we have:
\[ \begin{align*} S_f(n) &= \frac{1}{g(1)} \left( S_{f * g}(n) - \sum_{i:2\le d_i \le n} S_f\left( a_i \right) \left( S_g(d_{i+1}-1) - S_g(d_i-1) \right) \right) \nl &= 1 - \sum_{i:2\le d_i \le n} S_f\left( a_i \right) \frac{(d_{i+1}-1)d_{i+1}-d_i(d_i-1)}{2} \end{align*} \]
Using memoization, we can compute $S_f(n)$ in $O\left(N^{2/3}\right)$ time. The final sum is written as:
\[ \sum_{i:d_i \le N} \left( S_f(d_{i+1}-1) - S_f(d_i-1) \right) a_i^2 (a_i + 1) \]
The overall time complexity is $O\left(N^{2/3}+\sqrt{N}\right)=O\left(N^{2/3}\right)$, which is efficient enough for the given constraints.
