問題は次のように解釈できます。（問題文中の \(X, M\) を \(x = 2X, K = 2M\) で置き換えています）

連立合同方程式

\[x \equiv a_i \pmod {2a_i} \quad \forall 1 \leq i \leq N\]

を満たす \(1 \leq x \leq K\) の個数を求めよ。

条件 \(x \equiv a \pmod {2a}\) を、\(a = 2^b c\)（\(c\) は奇数）とおいて \(\bmod \ 2^{b+1}\) と \(\bmod \ c\) の条件に分けると公式解説の事実が導けますが、本解説ではいったんそのことは忘れて、より一般に次の問題を解くことを考えます。

連立合同方程式

\[x \equiv r_i \pmod {m_i} \quad \forall 1 \leq i \leq N\]

を満たす \(1 \leq x \leq K\) の個数を求めよ。

この連立合同方程式の解は次のいずれかの形です (CRT)。

• 解なし。
• ある \(r, m \: (0 \leq r < m)\) が存在して、\(x \equiv r \pmod m\) と書ける。

atcoder::crt を用いると、\(m\) が ll に収まるときにこの \((r, m)\) を求めることができます。本問の制約では \(r, m\) はとても大きくなりうるため、直接求めることはできません。しかし \(1\) 以上 \(K\) 以下の解の個数を求めるだけであれば、

• \(K < r\) のとき答えは \(0\)
• \(r \leq K < m\) のとき答えは \(\begin{cases}0 & (r = 0) \\ 1 & (r \geq 1)\end{cases}\)

となるため、\(\min(r, K+1)\) および \(\min(m, K+1)\) を求めれば十分です。そして CRT のアルゴリズムを考えると、これは実際に可能です。

以下 CRT のアルゴリズムの中身を解説しながら、\(\min(r, K+1)\) および \(\min(m, K+1)\) を求められることを説明します。

解が存在するとして、\(j \: (0 \leq j \leq N)\) 番目までの条件を考えたときの \(r, m\) を \(r'_j, m'_j\) とします。すなわち、

\[x \equiv r_i \pmod {m_i} \quad \forall 1 \leq i \leq j \iff x \equiv r'_j \pmod {m'_j}\]

です。

\(r'_j, m'_j\) を \(j = 0, 1, \dots, N\) の順に求めます。\((r'_0, m'_0) = (0, 1)\) です。\((r'_{j-1}, m'_{j-1})\) から \((r'_{j}, m'_{j})\) を求めるには

\[\begin{cases} x \equiv r'_{j-1} & \pmod {m'_{j-1}} \\ x \equiv r_j & \pmod {m_j} \end{cases}\]

を解けばよいです。すなわち、\(N=2\) の場合が解ければよいです。

\(N = 2\) の場合、条件はある \(k_1, k_2\) が存在して \(x = m_1k_1+ r_1 = m_2k_2 + r_2\) と書けることです。\(2\) つ目の等号を考えると \(1\) 次不定方程式

\[m_1k_1 - m_2k_2 = r_2 - r_1 \tag{*}\]

となっています。\(g = \gcd(m_1, m_2)\) とおくと、\((*)\) に解が存在する条件は \(r_2 - r_1\) が \(g\) で割り切れることです。拡張ユークリッドの互除法を用いて \(g\) および

\[m_1k'_1 - m_2k'_2 = g\]

を満たす \((k'_1, k'_2)\) を求めることができ、\((*)\) に解が存在するときの一般解はこの \(k'_1, k'_2\) を用いて

\[k_1 = k'_1 \frac{r_2 - r_1}{g} + \ell \frac{m_2}{g}, \quad k_2 = k'_2 \frac{r_2 - r_1}{g} + \ell \frac{m_1}{g}, \quad \ell \in \mathbb{Z}\]

と書けます。よってもとの \(x\) の連立合同方程式の解は

\[x \equiv r_1 + m_1 k'_1 \frac{r_2 - r_1}{g} \quad \left(\bmod \ {\frac{m_1m_2}{g}}\right)\]

です。

あまりを計算する際は、\(k_1 = k'_1 \dfrac{r_2 - r_1}{g} \bmod \dfrac{m_2}{g}\) とすると、\(0 \leq r_1 \leq m_1 - 1,\) \(0 \leq k_1 \leq \dfrac{m_2}{g} - 1\) より \(0 \leq r_1 + m_1k_1 \leq \dfrac{m_1m_2}{g} - 1\) となっていることを用いればよいです。

結局、アルゴリズムとしては

\[\begin{aligned} r &\leftarrow r + m \cdot \left(k'_1 \frac{r_i-r}{g} \bmod \dfrac{m_i}{g} \right), \\ m &\leftarrow m \cdot \dfrac{m_i}{g} \end{aligned}\]

のように更新していけばよいことになります。更新式から \(r, m\) はいずれも広義単調増加であるため、\(K\) を超えたらその時点で \(K+1\) にしてしまうことで \(\min(r, K+1)\) および \(\min(m, K+1)\) が計算できます。