[BOJ 1792] 공약수
https://www.acmicpc.net/problem/1792
Task
Compute:
\[ \abs{ \Set{ (x,y) | 1 \leq x \leq a, \; 1 \leq y \leq b, \; \gcd(x,y) = c } } \]
for $N$ queries $(a,b,c)$.
Solution
\[ \Set{ (x,y) | 1 \leq x \leq a, \; 1 \leq y \leq b, \; \gcd(x,y) = c } \nl = \Set{ (x^\prime, y^\prime) | 1 \leq x^\prime \leq \left\lfloor a/c \right\rfloor, \; 1 \leq y^\prime \leq \left\lfloor b/c \right\rfloor, \; \gcd(x^\prime,y^\prime) = 1 } \]
Denote $A = \left\lfloor a/c \right\rfloor$ and $B = \left\lfloor b/c \right\rfloor$.
Since $\sum_{d | n} \mu(d) = [n = 1]$, we have:
\[ \sum_{d | \gcd(x^\prime,y^\prime)} \mu(d) = [\gcd(x^\prime,y^\prime) = 1] \]
Thus:
\[ \begin{align*} & \abs{ \Set{ (x^\prime, y^\prime) | 1 \leq x^\prime \leq A, \; 1 \leq y^\prime \leq B, \; \gcd(x^\prime,y^\prime) = 1 } } \nl = & \sum_{x^\prime=1}^{A} \sum_{y^\prime=1}^{B} [\gcd(x^\prime,y^\prime) = 1] = \sum_{x^\prime=1}^{A} \sum_{y^\prime=1}^{B} \sum_{d | \gcd(x^\prime,y^\prime)} \mu(d) \nl = & \sum_{x^\prime=1}^{A} \sum_{y^\prime=1}^{B} \sum_{d \ge 1} \mu(d) [d | x^\prime ] [d | y^\prime ] \nl = & \sum_{d \ge 1} \mu(d) \sum_{x^\prime=1}^{A} [d | x^\prime] \sum_{y^\prime=1}^{B} [d | y^\prime ] = \sum_{d \ge 1} \mu(d) \left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor \nl = & \sum_{d=1}^{\min(A,B)} \mu(d) \left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor \end{align*} \]
Therefore, the answer for each query is:
\[ \sum_{d=1}^{\min(A,B)} \mu(d) \left\lfloor \frac{A}{d} \right\rfloor \left\lfloor \frac{B}{d} \right\rfloor \]
Optimization
Precomputing the Mobius function up to $\text{MAX}$ can be done in $O(\text{MAX} \log \log \text{MAX})$ time using a sieve method. If we compute each query naively, the time complexity is:
\[ O\left( N \min(A,B) \right) \]
and this is too slow. To optimize, we can group the terms with the same value of $\left\lfloor A/d \right\rfloor$ and $\left\lfloor B/d \right\rfloor$. Let $p(d) = \left\lfloor A/d \right\rfloor$ and $q(d) = \left\lfloor B/d \right\rfloor$. Denote $d_0 = 1$ and let $d_1, \ldots$ be the values of $d$ such that $p(d)$ or $q(d)$ changes. Relation between $d_i$ and $d_{i+1}$ is:
\[ d_{i+1} = \min\left( \left\lfloor \frac{A}{p(d_i)} \right\rfloor, \; \left\lfloor \frac{B}{q(d_i)} \right\rfloor \right) + 1 \]
If we denote $M(n) = \sum_{k=1}^{n} \mu(k)$, then the answer can be computed as:
\[ \sum_{i: d_i \leq \min(A,B)} \left( M(d_{i+1}-1) - M(d_i-1) \right) p(d_i) q(d_i) \]
The complexity of this approach is:
\[ O\left( N \sqrt{\min(A,B)} \right) \]
This is efficient enough for the given constraints.
