Contest Duration: - (local time) (210 minutes) Back to Home

## E - Three Traffic Lights Editorial by rng58_admin

Let $$m_i := g_i + r_i$$. We call a tuple $$(m_1, x_1, m_2, x_2, m_3, x_3)$$ nice if there exists an integer $$x$$ that satisfies $$x \equiv x_i \pmod {m_i}$$ for each $$i$$. Our task is to compute the number of tuples $$(i, j, k)$$ that satisfies:

• $$0 \leq i < g_1$$, $$0 \leq j < g_2$$, $$0 \leq k < g_3$$
• $$(m_1, i, m_2, j, m_3, k)$$ is nice

First, let’s try to solve some easy cases. For example, if $$m_1, m_2, m_3$$ are three distinct primes, the task is easy because all tuples with the modulos are nice.

Suppose that for some prime $$p$$, $$p$$ divides $$m_1$$ but not $$m_2$$ and $$m_3$$. Notice the following fact:

• $$(m_1, i, m_2, j, m_3, k)$$ is nice iff $$(m_1', i \% m_1', m_2, j, m_3, k)$$ is nice, where $$m_1' = m_1 / p$$.

Thus, we can “simplify” the modulos from $$(m_1, m_2, m_3)$$ to $$(m_1', m_2, m_3)$$.

A similar observation can be made when for some prime $$p$$, $$ord_p m_1 >\max \{ ord_p m_2, ord_p m_3 \}$$ holds:

• $$(m_1, i, m_2, j, m_3, k)$$ is nice iff $$(m_1', i \% m_1', m_2, j, m_3, k)$$ is nice, where $$m_1' = m_1 / p^t$$, where t = $$ord_p m_1 -\max \{ ord_p m_2, ord_p m_3 \}$$.

By repeating this simplification, we can assume the following conditions for the modulos:

• $$m_1$$ divides $$LCM(m_2, m_3)$$.
• $$m_2$$ divides $$LCM(m_1, m_3)$$.
• $$m_3$$ divides $$LCM(m_1, m_2)$$.

Now, we can prove that we can write $$m_1 = gab, m_2 = gac, m_3 = gbc$$ for some integers $$g, a, b, c$$. Without loss of generality, we can assume that $$a \leq b \leq c$$.

Now a brute force works! Let’s simulate all changes of the two lights $$2, 3$$ until time $$gabc = LCM(m_1, m_2, m_3)$$. Until then, the two lights change their colors $$O(a + b)$$ times. We can actually generate all changes because $$bc \leq gbc = m_3 \leq MAX = 10^{12}$$, $$a \leq b \leq \sqrt{bc}$$, and both $$a$$ and $$b$$ are $$O(\sqrt{MAX})$$.

posted:
last update: