\(m_i := g_i + r_i\) とします。組 \((m_1, x_1, m_2, x_2, m_3, x_3)\) に対し、ある整数 \(x\) が存在して各 \(i\) について \(x \equiv x_i \pmod {m_i}\) を満たすとき、この組を 良い 組と呼びます。この問題での目的は、以下の条件を満たす組 \((i, j, k)\) の個数を数えることです。

• \(0 \leq i < g_1\), \(0 \leq j < g_2\), \(0 \leq k < g_3\)
• \((m_1, i, m_2, j, m_3, k)\) は良い組

まず、簡単な場合を考えてみましょう。 例えば、\(m_1, m_2, m_3\) が三つとも異なる素数の場合は、その mod の全ての組が良い組となるため簡単です。

ある素数 \(p\) が存在して、\(p\) は \(m_1\) を割り切るが \(m_2, m_3\) は割り切らないとします。次の事実に注意します。

• \((m_1, i, m_2, j, m_3, k)\) が良い組であることは、\(m_1' = m_1 / p\) として \((m_1', i \% m_1', m_2, j, m_3, k)\) が良い組であることと同値である。

したがって、mod を \((m_1, m_2, m_3)\) から \((m_1', m_2, m_3)\) へと「簡約」できます。

同様の考察が、ある素数 \(p\) が存在して \(ord_p m_1 >\max \{ ord_p m_2, ord_p m_3 \}\) であるときに行えます。

• \((m_1, i, m_2, j, m_3, k)\) が良い組であることは、 t = \(ord_p m_1 -\max \{ ord_p m_2, ord_p m_3 \}\) として \((m_1', i \% m_1', m_2, j, m_3, k)\) が良い組であることと同値である。

この簡約を繰り返すことで、mod に対して次を仮定できます。

• \(m_1\) は \(LCM(m_2, m_3)\) を割り切る。
• \(m_2\) は \(LCM(m_1, m_3)\) を割り切る。
• \(m_3\) は \(LCM(m_1, m_2)\) を割り切る。

ここで、ある整数 \(g, a, b, c\) が存在して \(m_1 = gab, m_2 = gac, m_3 = gbc\) と書けることが証明できます。一般性を失うことなく、\(a \leq b \leq c\) と仮定できます。

これで全探索が行えます。時刻 \(gabc = LCM(m_1, m_2, m_3)\) までの信号機 \(2, 3\) の色の変化を全てシミュレートしましょう。それまでに起こる二機の色の変化は \(O(a + b)\) 回です。実は三機の色の変化を全て列挙することもできます。なぜなら \(bc \leq gbc = m_3 \leq MAX = 10^{12}\), \(a \leq b \leq \sqrt{bc}\) より \(a, b\) はともに \(O(\sqrt{MAX})\) であるからです。