TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

53.8% (7/13)

Submission's AC Ratio

14.0% (12/86)

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

For Testdata: 0 ~ 2, Score: 12
For Testdata: 3 ~ 7, Score: 23
For Testdata: 3 ~ 12, Score: 31
For Testdata: 0 ~ 15, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 2097152 65536
1 10000 2097152 65536
2 10000 2097152 65536
3 1000 2097152 65536
4 1000 2097152 65536
5 1000 2097152 65536
6 1000 2097152 65536
7 1000 2097152 65536
8 1000 2097152 65536
9 1000 2097152 65536
10 1000 2097152 65536
11 1000 2097152 65536
12 1000 2097152 65536
13 5000 2097152 65536
14 5000 2097152 65536
15 5000 2097152 65536