[BOJ 19549] 레이저 연구소

in Computer Science on Problem Solving · 11 min

https://www.acmicpc.net/problem/19549

Task

We have an $N\times M$ grid of unit squares:

  • $(N+1)(M+1)$ buildings at grid points
  • $2NM + N + M$ walls on edges

A laser is fired between every pair of buildings (not parallel to x/y axes).
Each shot burns:

  • all buildings on the line (cost $A$ each)
  • all crossed walls (cost $B$ each)

After every shot, everything is repaired.
Find the total repair cost for all valid laser shots.

Solution

Suppose firing a laser from building $(0,0)$ to $(n,m)$.

  • It burns $\gcd(n,m) + 1$ buildings.
  • It crosses $(n-\gcd(n,m)) + (m-\gcd(n,m)) = n+m-2\gcd(n,m)$ walls.

Thus, the cost for this shot is:

\[ A + (n+m)B + \gcd(n,m)(A - 2B) \]

To find the total cost, we sum over all pairs of buildings. There are $(N+1-n)(M+1-m)$ pairs of buildings with relative position $(n,m)$. Also, we can fire lasers in four distinct ways for each pair, since there are two diagonals and two directions for each rectangle. Thus, the total cost is:

\[ 4 \sum_{i=1}^{N} \sum_{j=1}^{M} (N+1-i)(M+1-j) \left( A + (i+j)B + \gcd(i,j)(A - 2B) \right) \]

We can sum up the first two terms easily.

\[ 4 \sum_{i=1}^{N} \sum_{j=1}^{M} (N+1-i)(M+1-j) A = 4 \sum_{i=1}^{N} \sum_{j=1}^{M} Aij = AN(N+1)M(M+1) \nl \]

\[ \begin{aligned} & 4 \sum_{i=1}^{N} \sum_{j=1}^{M} (N+1-i)(M+1-j) (i+j)B \nl = & 4 \sum_{i=1}^{N} \sum_{j=1}^{M} i(N+1-i)jB + 4 \sum_{i=1}^{N} \sum_{j=1}^{M} j(N+1-i)jB \nl = & 4 \cdot \frac{N(N+1)(N+2)}{6} \cdot \frac{M(M+1)}{2} B + 4 \cdot \frac{M(M+1)(M+2)}{6} \cdot \frac{N(N+1)}{2} B \nl = & \frac{BN(N+1)M(M+1)(N+M+4)}{3} \end{aligned} \]

To compute the last term, let’s define a sum:

\[ S_{ab} = \sum_{i=1}^{N} \sum_{j=1}^{M} i^a j^b \gcd(i,j) \]

Then, we can express the last term as:

\[ 4(A - 2B) \left[ (N+1)(M+1) S_{00} - (N+1) S_{01} - (M+1) S_{10} + S_{11} \right] \]

Then, the total cost is:

\[ N(N+1)M(M+1) \left( A + \frac{B(N+M+4)}{3} \right) + 4(A - 2B) \left[ (N+1)(M+1) S_{00} - (N+1) S_{01} - (M+1) S_{10} + S_{11} \right] \]

Now, we need to compute $S_{ab}$ efficiently. Let’s transform the sum by grouping terms with the same gcd.

\[ \begin{aligned} S_{ab} & = \sum_{i=1}^{N} \sum_{j=1}^{M} i^a j^b \gcd(i,j) \nl & = \sum_{i=1}^N \sum_{j=1}^M i^a j^b \sum_{d=1}^{\min(i,j)} d \cdot [\gcd(i,j) = d] \nl & = \sum_{d=1}^{\min(N,M)} \sum_{i=1}^{\lfloor N/d \rfloor} \sum_{j=1}^{\lfloor M/d \rfloor} (di)^a (dj)^b d \cdot [\gcd(i,j) = 1] \nl & = \sum_{d=1}^{\min(N,M)} \sum_{i=1}^{\lfloor N/d \rfloor} \sum_{j=1}^{\lfloor M/d \rfloor} d^{a+b+1} i^a j^b \sum_{t|i,j} \mu(t) \nl & = \sum_{d=1}^{\min(N,M)} \sum_{t\ge 1} d^{a+b+1} \mu(t) \sum_{i=1}^{\lfloor N/dt \rfloor} \sum_{j=1}^{\lfloor M/dt \rfloor} (it)^a (jt)^b \nl & = \sum_{d=1}^{\min(N,M)} \sum_{t\ge 1} d^{a+b+1} t^{a+b} \mu(t) \sum_{i=1}^{\lfloor N/dt \rfloor} i^a \sum_{j=1}^{\lfloor M/dt \rfloor} j^b \nl & = \sum_{k=1}^{\min(N,M)} \sum_{t|k} \frac{k^{a+b+1}}{t} \mu(t) \sum_{i=1}^{\lfloor N/k \rfloor} i^a \sum_{j=1}^{\lfloor M/k \rfloor} j^b \nl & = \sum_{k=1}^{\min(N,M)} k^{a+b+1} \cdot \frac{\phi(k)}{k} \cdot S_{\text{Id}_a}\left(\left\lfloor \frac{N}{k} \right\rfloor\right) S_{\text{Id}_b}\left(\left\lfloor \frac{M}{k} \right\rfloor\right) \nl & = \sum_{d=1}^{\min(N,M)} d^{a+b} \phi(d) S_{\text{Id}_a}\left(\left\lfloor \frac{N}{d} \right\rfloor\right) S_{\text{Id}_b}\left(\left\lfloor \frac{M}{d} \right\rfloor\right) \end{aligned} \]

where $S_{\text{Id}_k}(n) = \sum_{d=1}^{n} d^k$. We can compute $S_{\text{Id}_k}(n)$ in $O(1)$ time using the formulas for sums of powers. Grouping by values of $\lfloor N/d \rfloor$ and $\lfloor M/d \rfloor$, we can reduce the number of terms in the sum to $O(\sqrt{N} + \sqrt{M})$. By denoting as $d_0 = 1$, $p_i = \lfloor N/d_i \rfloor$, $q_i = \lfloor M/d_i \rfloor$, and

\[ d_{i+1} = \min\left(\left\lfloor \frac{N}{p_i} \right\rfloor, \left\lfloor \frac{M}{q_i} \right\rfloor\right) + 1 \]

By defining $f(d) = d^{a+b} \phi(d)$, the sum can be computed as:

\[ \sum_{i:d_i \le \min(N,M)} \left( S_f(d_{i+1}-1) - S_f(d_i-1) \right) S_{\text{Id}_a}(p_i) S_{\text{Id}_b}(q_i) \]

Now what remains is to compute $S_f$ efficiently. By using the Mertens trick, we can compute $S_f(n)$ in $O\left(n^{2/3}\right)$ time. Using the relationship $f * \text{Id}_{a+b} = \text{Id}_{a+b+1}$, we have:

\[ \begin{aligned} S_f(n) & = \frac{1}{\text{Id}_{a+b}(1)} \left( S_{\text{Id}_{a+b+1}}(n) - \sum_{i:2\le d_i \le n} S_f\left( a_i \right) \left( S_{\text{Id}_{a+b}}(d_{i+1}-1) - S_{\text{Id}_{a+b}}(d_i-1) \right) \right) \nl & = S_{\text{Id}_{a+b+1}}(n) - \sum_{i:2\le d_i \le n} S_f\left( a_i \right) \left( S_{\text{Id}_{a+b}}(d_{i+1}-1) - S_{\text{Id}_{a+b}}(d_i-1) \right) \end{aligned} \]

Since $S_{\text{Id}_k}(n)$ can be computed in $O(1)$ time, we can compute all required $S_f(n)$ values using memoization in $O\left(N^{2/3}+M^{2/3}\right)$ time. Thus, the overall time complexity is $O\left(N^{2/3}+M^{2/3}+\sqrt{N}+\sqrt{M}\right) = O\left(N^{2/3}+M^{2/3}\right)$, which is efficient enough for the given constraints.