TopCoder

Thumb a
$ $
$ \color{red}{\href{../users/icube}{\circ Inactive}} $

User's AC Ratio

96.2% (25/26)

Submission's AC Ratio

33.1% (60/181)

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

For Testdata: 0 ~ 4, Score: 5
For Testdata: 5 ~ 9, Score: 10
For Testdata: 10 ~ 14, Score: 15
For Testdata: 15 ~ 19, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536