C2101 - 巧克力金币交易

C2102 - 巧克力金币四子棋

Use depth-first search (DFS) to simulate every move possible up until depth $ m $. This is usually accomplished with a recursive function: for every legal move, play it and call the function again, and then undo it.

Apart from the last move, it is necessary to check that both 小巧 and 小克 do not win, i.e. connect 4 of their discs horizontally, vertically or diagonally ($ y = x $ or $ y = -x $).

C2103 - 巧克力金币节

The minimum distance of each node from the source node in a graph can be calculated with breadth-first search (BFS):

• Create a distance array $ dist $.
• Push the source node $ s $ into the queue, and mark $ dist[s] = 0 $.
• While the queue is not empty, pop the first node $ u $ from the queue.
• For each unvisited neighboring node $ v $ of $ u $, mark $ dist[v] = dist[u] + 1 $ and push $ v $ into the queue.

There is no need to run BFS once for every factory / target city. Simply push every factory into the queue in the beginning.
The answer to the problem is $ \displaystyle\max_{1 \le i \le k} dist[d_i] $.

C2104 - 巧克力金币危机

First I have to apologize for the wrong test cases. I made this task in 1 day during the uniform test and I dont have time for testing. The solution given after the lesson is also wrong, it actually needs a very advanced method to solve. Anyways, here is the method.

Hint

The line connecting the point $(x,y)$ is repeated if and only if $gcd(x, y) \neq 1$. Why?
It is because the slope, $\dfrac{y}{x}$, can be simplified to $\dfrac{\frac{y}{\gcd(x, y)}}{\frac{x}{\gcd(x, y)}}$, and will equal to one of the lines, thus repeated.

Subtask 1 (50%)

Set a counter to be initally at 2. It represents the horizontal and vertical lines from $(0, 0)$, which exists in every case. Repeat for each point $(x, y), 1 \le x \le n, 1 \le y \le m$. If $\gcd(x, y) = 1$, then add 1 to the counter. At last, output the counter. This method have a time complexity of $O(nm)$.

Full solution (100%)

Requires linear sieve and mobius inversion.
The mobius function have the following formula: .
This problem is asking for: $$\sum_{1\le i\le n}\sum_{1\le j\le m}[\gcd(i, j) = 1]$$ Apply the mobius inverse formula, $$\sum_{1\le i\le n}\sum_{1\le j\le m}\sum_{d|\gcd(i, j)} \mu (d)$$ $d|\gcd(i, j)$ is equivalent to $[d|i][d|j]$. We can sum $d$ from 1 to $\min(n, m)$. $$\sum_{1\le i\le n}\sum_{1\le j\le m}\sum_{1\le d \le \min(n, m)} [d|i] [d|j] \mu (d)$$ $$\sum_{1\le d \le \min(n, m)}\sum_{1\le i\le n}\sum_{1\le j\le m} [d|i] [d|j] \mu (d)$$ $$\sum_{1\le d \le \min(n, m)} \mu (d)\left(\sum_{1\le i\le n} [d|i] \right) \left(\sum_{1\le j\le m} [d|j] \right)$$ $$\sum_{1\le d \le \min(n, m)} \mu (d) \left(\left \lfloor{\frac{n}{d}}\right \rfloor \right) \left(\left \lfloor{\frac{m}{d}}\right \rfloor \right)$$

Now we just need to compute the mobius function in linear time. It can be achieved by linear sieve. The mobius function has the following properties:

• $\mu(n) = 1$ if $n$ is a square-free positive integer with an even number of prime factors.
• $\mu(n) = -1$ if $n$ is a square-free positive integer with an odd number of prime factors.
• $\mu(n) = 0$ if $n$ has a squared prime factor.
• is multiplicative, that is, $\mu(ab) = \mu(a) \mu(b)$ if $gcd(a, b) = 1$

Using these properties, we can compute it by,

With the above formula, the answer can then be computed in linear time.