TopCoder

User's AC Ratio

59.0% (23/39)

Submission's AC Ratio

22.3% (68/305)

Description

給你$N$個數,請計算某一個區間內的所有數的最小公倍數。

Input Format

第一行有兩個正整數$1\leq N, Q\leq 10^ 6$,代表數字個數以及詢問個數。
第二行有$N$個數$1\leq c_1, c_2, \dots, c_N\leq 10^ 6$。
接著有$Q$行,每一行都有兩個正整數$1\leq l\leq r\leq N$,代表要詢問$c_l,\dots,c_r$的最小公倍數。

子任務(測資) 額外限制 分數
1 (0~2) $c_i\leq 40$ 12
2 (3~7) $N,Q,c_i\leq 10^ 4$ 23
3 (3~12) $N,Q,c_i\leq 10^ 5$ 31
4 (0~15) 無限制 34

Output Format

對於每個詢問,請輸出一行,包含一個正整數,代表區間的最小公倍數。由於答案很大,請將答案模1000000007後輸出。

Sample Input

5 2
2 3 5 7 4
1 4
1 5

Sample Output

210
420

Hints

建議C++輸入輸出使用者加入cin.tie(0);以及ios_base::sync_with_stdio(0)兩行,以\n代替endl,同時不要使用C式輸出。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第五次模擬賽pF
題目取自2015 TOI第二階段選訓第四次模擬考pC

Subtasks

No. Testdata Range Score
1 0~2 12
2 3~7 23
3 3~12 31
4 0~15 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 10000 2097152 262144 1 4
1 10000 2097152 262144 1 4
2 10000 2097152 262144 1 4
3 1000 2097152 262144 2 3 4
4 1000 2097152 262144 2 3 4
5 1000 2097152 262144 2 3 4
6 1000 2097152 262144 2 3 4
7 1000 2097152 262144 2 3 4
8 1000 2097152 262144 3 4
9 1000 2097152 262144 3 4
10 1000 2097152 262144 3 4
11 1000 2097152 262144 3 4
12 1000 2097152 262144 3 4
13 5000 2097152 262144 4
14 5000 2097152 262144 4
15 5000 2097152 262144 4