1282 . 愛蜜利雅的作業2

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

90.8% (69/76)

Submission's AC Ratio

25.3% (154/609)

Tags

HSNUcon CKsim 2016-CKsim-3rd 2016-HSNUcon

Description

這一天 羅茲瓦爾 為了 讓愛蜜莉雅更接近王，於是 丟了一道問題給她，可是愛蜜莉雅發現自己好像做不 出來 ，於是她想請你幫忙解決這個問題。
問題如下 :
「程序題 :給定一個 給定一個N項正整數序列，有Q次操作 ， 每次操作有兩種type，type 1 將區間每個元素都 將區間每個元素都加上一個正整數k，type 2輸出一個區間中所有數字的最大公因數」
愛蜜莉亞知道你是程式高手，希望能幫忙解決 這個問題，若你能解出來說不定就看到她那燦爛的笑容喔(maybe就像以下這樣 ) (謎之音 :我想看我想看 > /// < 看我速把這題AC掉吧XD )。

Input Format

第一行 有兩個正整數N、Q，分別代表這個正整數列的項數，及詢問次數。
接下來一行有N個正整數，代表該數列每一項的數字。
接下來Q行，每行以1或2開頭 :
若以1開頭 ，隨後會有三個正整數l,r,k(1≤l≤r≤N)，此操作為將區間[l,r]中每個數字加上k
若以2開頭，隨後會有兩個正整數l,r(1≤l≤r≤N)，此操作為詢問，請輸出區間 [l,r]中所有數字的最大公因數。

保證過程中數列的每個數字皆小於等於262

子任務（測資） 額外限制 分數
1 (0~4) 1≤N≤103,1≤Q≤103 5
2 (5~9) 1≤N≤105,1≤Q≤105，無type 1的操作 10
3 (10~14) 1≤N≤105,1≤Q≤105，若操作為type 1，則l=r 15
4 (15~19) 1≤N≤105,1≤Q≤105 70

Output Format

對於每個詢問操作，輸出該的區間所有元素 的最大公因數。

Sample Input 1

5 1
1 2 3 4 5
2 1 5

Sample Output 1

1

Hints

Problem Source

Problem and Description by 殿仁．王
Set by Paupière
建國中學105學年度校內第三次模擬賽pB
題目取自2016年附中資訊校內賽Task 7

Subtasks

No. Testdata Range Score
1 0~4 5
2 5~9 10
3 10~14 15
4 15~19 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 1
4 1000 65536 262144 1
5 1000 65536 262144 2
6 1000 65536 262144 2
7 1000 65536 262144 2
8 1000 65536 262144 2
9 1000 65536 262144 2
10 1000 65536 262144 3
11 1000 65536 262144 3
12 1000 65536 262144 3
13 1000 65536 262144 3
14 1000 65536 262144 3
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4
Submit
Back to Top