1872 . 最小公倍數

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

i_am_noob
施～～廣～～霖～～

User's AC Ratio

64.8% (57/88)

Submission's AC Ratio

19.9% (130/653)

Tags

TOI 2015-TOI-4th CKsim 2016-CKsim-5th

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 1

5 2
2 3 5 7 4
1 4
1 5

Sample Output 1

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 (VSS, KiB) Output Limit (KiB) Subtasks
0 10000 2097152 262144 1 4
1 10000 2097152 262144 1 4
2 10000 2097152 262144 1 4
3 1200 2097152 262144 2 3 4
4 1200 2097152 262144 2 3 4
5 1200 2097152 262144 2 3 4
6 1200 2097152 262144 2 3 4
7 1200 2097152 262144 2 3 4
8 1500 2097152 262144 3 4
9 1500 2097152 262144 3 4
10 1500 2097152 262144 3 4
11 1500 2097152 262144 3 4
12 1500 2097152 262144 3 4
13 5000 2097152 262144 4
14 5000 2097152 262144 4
15 5000 2097152 262144 4
Submit
Back to Top