简单数论题
题目描述
给出一个长度为 $n$ 的序列 $a$，$q$ 次询问 $\prod_{i=l}^r \operatorname{lcm}(a_i,x)$ 的值。
答案对 $10 ^ 9 + 7$ 取模。
输入输出格式
输入格式
第一行两个整数 $n,q$。
第二行 $n$ 个整数 $a_i$。
接下来 $q$ 行，每行三个整数 $l,r,x$。
输出格式
$q$ 行，一行一个答案。
输入输出样例
输入样例 #1
5 5
12 8 9 14 21
1 5 2
1 3 3
3 5 7
1 5 6
2 3 7输出样例 #1
1016064
2592
18522
9144576
3528
输入样例 #2
10 10
47 47 47 3 7 19 2 7 31 31
1 3 53
4 4 61
2 8 73
6 7 53
1 5 47
2 5 73
5 6 71
7 7 67
4 7 83
1 9 59
输出样例 #2
456856666
183
802334105
106742
816245119
365992530
670453
134
871739899
194416112
输入样例 #3
10 10
2 13 13 2 3 17 11 19 19 7
4 8 1
1 2 7
6 7 37
9 10 7
1 8 9
3 8 47
5 8 2
3 6 9
4 5 25
4 5 8
输出样例 #3
21318
1274
256003
931
819082258
40076077
170544
2899962
3750
192
输入样例 #4
10 10
14 39 31 30 3 21 19 17 35 2
1 3 10
6 6 19
2 4 3
6 8 18
1 10 2
5 6 49
2 6 8
7 9 26
3 6 12
1 1 10
输出样例 #4
8463000
399
108810
13186152
23723126
21609
437603581
198696680
22498560
70
说明
**【样例解释】**
对于样例一的第二个查询，答案是：
$\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$ 为正整数。