真的一点都不卡啊……
首先这个最大公倍数 \(\text{G}\) 明显是诈骗，如果 \(\text{G}\nmid \text{L}\) 一定无解，直接判掉。否则我们将 \(\text{L},\text{X}\) 和 \(\text{N}\) 都除 \(\text{G}\)：\(\text{N}\) 之所以能直接除 \(\text{G}\) 是因为你取出来的数都必须是 \(\text{G}\) 的因数。而 \([1,\text{N}]\) 中有 \(\left\lfloor\frac{\text{N}}{\text{G}}\right\rfloor\) 个数满足这个条件。
然后问题变为：
从 \([1,\text{N}]\) 中取若干数，\(\text{Q}\) 次询问，每次查询必须包含 \(\text{X}\) 的取数方案，使得 \(\text{gcd}\) 为 \(1\) 并且 \(\text{lcm}\) 为 \(\text{L}\)。
显然我们取的数都是 \(\text{L}\) 的因数，于是可以对 \(\text{L}\) 质因数分解。假设质数 \(p\) 的次数为 \(r_p\)。其次，\(\text{L}\) 的因数最多有 \(d=768\) 个，记为集合 \(\mathbb{F}\)。
由于 \(\omega(10^8)=8\)，并且我们只关心每个数的质因子 \(p\) 次数是否为 \(0\) 或者 \(r_p\)，所以考虑状压。可以对于每个 \(x\in\mathbb{F}\)，将 \(x\) 的状态表示为一个 \(16\) 位的二进制数：前 \(8\) 位表示每个 \(p\) 的次数是否为 \(0\)，后 \(8\) 位表示每个 \(p\) 的次数是否为 \(r_p\)。
这一步预处理是 \(O(d\omega(\text{L})+\text{N})\) 的，写得再臭都能过。
先不考虑 \(\text{X}\) 的限制，答案就是取出若干个数，或起来为全集的方案数，将或起来为 \(S\) 的答案设为 \(f_S\)。
这是典，考虑容斥：令 \(g_S\) 为或起来是 \(S\) 的子集的方案数。\(g_S=\sum\limits_{T\subseteq S}f_T\)，于是 \(f_S=\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}g_T\)。由于答案 \(S\) 为全集，并且 \(|S|=2\omega(\text{L})\)，所以 \(\text{ans}=\sum\limits_T(-1)^{|T|}g_T\)。
考虑到 \(g_S=2^{c(S)}\)。\(c(S)\) 为 \([1,\text{N}]\) 的数状态表示为 \(S\) 子集的个数，显然可以用 FWT 求出，做一遍子集和即可。
现在考虑有 \(\text{X}\) 的限制，改变 \(f,g\) 的定义为必须选 \(\text{X}\) 时，相应的意义。于是 \(g_S=[\text{X}\subseteq S]2^{c(S)-1}\)，即减去不选 \(\text{X}\) 的方案。
注意到 \(\text{ans}=\sum\limits_T(-1)^{|T|}g_T\) 仍然成立。所以：
考虑预处理出所有的 \(\text{ans}(\text{X})\)，这东西显然是个超集和，也可以 FWT 做。做完了，复杂度 \(O(n+\omega(\text{L})(d+2^{\omega(\text{L})}))\)。
真的一点也不卡常。在 LOJ 上只跑了 143 ms。