[BOJ 13714] 약수의 개수
https://www.acmicpc.net/problem/13714
Task
Compute:
\[ \sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} \tau(ijk) \]
for given integers $a$, $b$, and $c$, where $\tau(n)$ is the number of divisors of $n$.
Solution
Computing directly is inefficient. Instead, we observe that:
\[ \sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} \tau(ijk) = \sum_{m=1}^{ab} \abs{ \Set{ (i,j) | 1 \leq i \leq a, \; 1 \leq j \leq b, \; ij = m } } \sum_{k=1}^{c} \tau(mk) \]
Denote:
\[ f(m) = \abs{ \Set{ (i,j) | 1 \leq i \leq a, \; 1 \leq j \leq b, \; ij = m } } \nl S(m) = \sum_{k=1}^{c} \tau(mk) \]
Then, we have:
\[ \sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} \tau(ijk) = \sum_{m=1}^{ab} f(m) S(m) \]
Computing $f(m)$ up to $ab$ can be done naively in $O(ab)$ time. Let’s focus on computing $S(m)$ efficiently.
\[ S(m) = \sum_{k=1}^{c} \sum_{t | mk} 1 = \sum_{t=1}^{mc} \abs{ \Set{ k | 1 \leq k \leq c, \; t | mk } } \]
Let’s denote $u=\gcd(t,m)$ and $t=us, m=uq$. Then, $t | mk$ is equivalent to $s | k$. Thus, we have:
\[ \abs{ \Set{ k | 1 \leq k \leq c, \; t | mk } } = \abs{ \Set{ k | 1 \leq k \leq c, \; s | k } } = \left\lfloor \frac{c}{s} \right\rfloor \]
Therefore, we can rewrite $S(m)$ as:
\[ S(m) = \sum_{q | m} \sum_{\substack{1 \leq s \leq c \nl \gcd(s,q) = 1}} \left\lfloor \frac{c}{s} \right\rfloor \]
Let’s denote:
\[ G(q) = \sum_{\substack{1 \leq s \leq c \nl \gcd(s,q) = 1}} \left\lfloor \frac{c}{s} \right\rfloor \]
Then, we have:
\[ S(m) = \sum_{q | m} G(q) \]
Now we need to compute $G(q)$ efficiently. Using the property of the Mobius function, we have:
\[ \begin{align*} G(q) &= \sum_{s=1}^{c} \left\lfloor \frac{c}{s} \right\rfloor [\gcd(s,q) = 1] \nl &= \sum_{s=1}^{c} \left\lfloor \frac{c}{s} \right\rfloor \sum_{d | \gcd(s,q)} \mu(d) \nl &= \sum_{d | q} \mu(d) \sum_{s=1}^{c} \left\lfloor \frac{c}{s} \right\rfloor [d | s] \nl &= \sum_{d | q} \mu(d) \sum_{s^\prime=1}^{\left\lfloor c/d \right\rfloor} \left\lfloor \frac{c}{d s^\prime} \right\rfloor \end{align*} \]
The inner sum only depends on $d$, so let’s denote it as $A(d)$. Summarizing, we have:
\[ \begin{align*} f(m) &= \abs{ \Set{ (i,j) | 1 \leq i \leq a, \; 1 \leq j \leq b, \; ij = m } } \nl A(d) &= \sum_{s^\prime=1}^{\left\lfloor c/d \right\rfloor} \left\lfloor \frac{c}{d s^\prime} \right\rfloor \nl G(q) &= \sum_{d | q} \mu(d) A(d) \nl S(m) &= \sum_{q | m} G(q) \nl \sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{k=1}^{c} \tau(ijk) &= \sum_{m=1}^{ab} f(m) S(m) \end{align*} \]
Complexity
Precomputing the Mobius function up to $ab$ can be done in $O(ab \log \log ab)$ time using a sieve method. Computing $f(m)$ up to $ab$ takes $O(ab)$ time. Computing $A(d)$ up to $c$ takes $O(c \log c)$ time. Computing $G(q)$ up to $ab$ takes $O(ab \log c)$ time. Computing $S(m)$ up to $ab$ takes $O(ab \log ab)$ time. Finally, computing the final sum takes $O(ab)$ time. Constraints are given as $1 \leq a, b, c \leq N$. Thus, the overall time complexity is:
\[ O\left( N^2 \log N \right) \]
This is efficient enough for the given constraints.
