TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 $$AC \approx (111111111)_2$$

User's AC Ratio

95.7% (45/47)

Submission's AC Ratio

25.5% (99/388)

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\leq l\leq r\leq N$),此操作為將區間$[l , r]$中每個數字加上$k$
若以2開頭,隨後會有兩個正整數$l , r$($1\leq l\leq r\leq N$),此操作為詢問,請輸出區間 $[l , r]$中所有數字的最大公因數。

保證過程中數列的每個數字皆小於等於$2^ {62}$

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

Output Format

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

Sample Input

5 1
1 2 3 4 5
2 1 5

Sample Output

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 (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