\(A_i \leq C_i \leq B_i\) かつ全ての要素が \(g\) の倍数であるような数列の個数は \(\prod \left(\left\lfloor \frac{B_i}{g} \right\rfloor - \left\lfloor \frac{A_i - 1}{g} \right\rfloor\right)\) です。

\(g\) を大きくしていったとき、\(\left\lfloor \frac{n}{g} \right\rfloor\) が変化する回数は \(O(\sqrt n)\) 回で、容易に列挙することができます。これを用いると、\(\left\lfloor \frac{B_i}{g} \right\rfloor - \left\lfloor \frac{A_i - 1}{g} \right\rfloor = 0\) となる \(i\) の個数と、そうでない \(i\) に対する \(\prod \left(\left\lfloor \frac{B_i}{g} \right\rfloor - \left\lfloor \frac{A_i - 1}{g} \right\rfloor\right)\) を imos 法の要領で管理することができます。

よって、\(K = \max(A_1, \dots, A_N, B_1, \dots, B_N, M)\) とおくと全ての要素が \(g\) の倍数であるような数列の個数を \(O(K\sqrt K)\) で求めることができるので、倍数メビウス変換を施すことにより問題への答えを求めることができます。

実装において多くの除算が登場するので定数倍が重めとなっています。ご注意ください。

実装例 (C++, 2819ms)