题目描述
Problem Description
Given a sequence \( a \) of length \( n \), and \( q \) queries asking for the value of \( \prod_{i=l}^r \operatorname{lcm}(a_i, x) \).
The answer should be taken modulo \( 10^9 + 7 \).
Input Format
The first line contains two integers \( n \) and \( q \).
The second line contains \( n \) integers \( a_i \).
The next \( q \) lines contain three integers each: \( l \), \( r \), and \( x \).
Output Format
Output \( q \) lines, each containing one answer.
Sample Input and Output
Input Sample #1
5 5
12 8 9 14 21
1 5 2
1 3 3
3 5 7
1 5 6
2 3 7
Output Sample #1
1016064
2592
18522
9144576
3528
Input Sample #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
Output Sample #2
456856666
183
802334105
106742
816245119
365992530
670453
134
871739899
194416112
Input Sample #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
Output Sample #3
21318
1274
256003
931
819082258
40076077
170544
2899962
3750
192
Input Sample #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
Output Sample #4
8463000
399
108810
13186152
23723126
21609
437603581
198696680
22498560
70
Notes
[Sample Explanation]
For the second query in Sample #1, the answer is:
\[ \operatorname{lcm}(12, 3) \times \operatorname{lcm}(8, 3) \times \operatorname{lcm}(9, 3) = 12 \times 24 \times 9 = 2592 \]
[Data Range]
This problem uses batched testing.
-
For \( 100\% \) of the data: \( 1 \le l \le r \le n \), \( 1 \le n, q, a_i, x \le 2 \times 10^5 \).
-
Detailed Data Range:
| Subtask Number | \( n, q, a_i, x \le \) | Special Properties | Score |
|---|---|---|---|
| 1 | 100 | None | 10 |
| 2 | \( 2 \times 10^5 \) | \( a_i, x \) are primes, \( a_i \neq x \) | 10 |
| 3 | \( 5 \times 10^4 \) | \( a_i \) are primes | 15 |
| 4 | \( 5 \times 10^4 \) | \( \mu(a_i) \neq 0 \) | 15 |
| 5 | \( 5 \times 10^4 \) | None | 25 |
| 6 | \( 2 \times 10^5 \) | None | 25 |
[Hints]
-
Sample #2 satisfies the special properties of Subtask 2, Sample #3 satisfies the special properties of Subtask 3, and Sample #4 satisfies the special properties of Subtask 4.
-
\( \mu(x) \) is the Möbius function, defined as follows:
Let \( x = p_1^{q_1} \times p_2^{q_2} \times \ldots \times p_k^{q_k} \).
\[ \mu(x) = \begin{cases} 1 & \text{if } x = 1 \\ (-1)^k & \text{if } q_1, q_2, \ldots, q_k \le 1 \\ 0 & \text{otherwise} \end{cases} \]
Note: \( p_i \) are primes, and \( q_i \) are positive integers.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分