P6217 简单数论题

给出一个长度为 $n$ 的序列 $a$，$q$ 次询问 $\prod_{i=l}^r \operatorname{lcm}(a_i,x)$ 的值。 答案对 $10 ^ 9 + 7$ 取模。

无

无

**【样例解释】** 对于样例一的第二个查询，答案是： $\quad \operatorname{lcm}(12,3) \times \operatorname{lcm}(8,3) \times \operatorname{lcm}(9,3)$ $= 12 \times 24 \times 9$ $= 2592$ ------------------ **【数据范围】** **本题采用捆绑测试。** - 对于 $100 \%$ 的数据：$1 \le l \le r \le n$，$1 \le n,q,a_i,x \le 2 \times 10 ^ 5$。 - **详细的数据范围：** | Subtask 编号 | $n,q ,a_i,x\le $ | 特殊性质 | 分值 | | :---------: | :---------------: | :---------------------------------: | :--: | | $1$ | $100$ | 无 | $10$ | | $2$ | $2 \times 10 ^ 5$ | $a_i,x$ 是质数，任意 $a_i \neq x$ | $10$ | | $3$ | $5 \times 10 ^ 4$ | $a_i$ 是质数 | $15$ | | $4$ | $5 \times 10 ^ 4$ | $μ(a_i) \neq 0$ | $15$ | | $5$ | $5 \times 10 ^ 4$ | 无 | $25$ | | $6$ | $2 \times 10 ^ 5$ | 无 | $25$ | ------------------------- **【提示】** - 样例二满足 Subtask2 的特殊性质，样例三满足 Subtask3 的特殊性质，样例四满足 Subtask4 的特殊性质。 - $μ(x)$ 是莫比乌斯函数，它的定义如下： 设 $x = {p_1} ^ {q_1} \times {p_2} ^ {q_2} \times ... \times {p_k} ^ {q_k}$。 $μ(x) =\begin{cases}1&x=1\\(-1) ^ k&q_1,q_2...q_k \le 1\\0&\text{otherwise}\end{cases}$ 注：$p_i$ 为质数，$q_i$ 为正整数。