1836 . [IOI 2013] 遊戲 Game
TopCoder
Tags
Description
巴勒與夏拉正在玩一個遊戲。遊戲盤是一個由R 列（以0, …, R – 1 標示）乘以C 行（以0, …,C – 1 標示）單元（cells）所構成的網格（grid）。我們以 (P, Q) 來表示位於第P 列、第Q 行的單元。每個單元包含一個非負整數，遊戲一開始時所有單元的值皆初始化為0。
遊戲進行的方式如下：在任何時間點，巴勒可以
•更新（update）一個單元 (P, Q) 所包含的整數值。
•要求夏拉計算一個矩形區域裡全部單元所包含數值的最大公因數（greatest common divisor，GCD），這個矩形透過給定其兩個對角 (P, Q) 與 (U, V) 來定義（對角單元包含在矩形內）。
巴勒在玩膩這個遊戲而跑到外面玩板球（cricket）前，最多將進行NU + NQ 個動作（更新NU次及要求計算NQ 次）。
你的任務是算出正確的答案。
Input Format
第一行有三個數字R C N，表示遊戲盤大小與巴勒的動作次數。
接下來 N 行，依照動作發生的順序，一個動作一行，表示動作的那一行必須是以下其中一種格式：
•1 P Q K，表示更新(P,Q)的值為K。
•2 P Q U V，表示查詢以(P, Q) 與 (U, V)為兩對角所構成的矩形內所有元素的最大公因數。
限制：
•1 ≤ R, C ≤ 109
•0 ≤ K ≤ 1018 ，K 是巴勒放置於網格單元的任何整數值。
Output Format
對於每個查詢，輸出一個數字表示答案，每個數字佔一行。
Sample Input 1
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1
Sample Output 1
4
1
2
Hints
R = 2 而C = 3，並且巴勒一開始進行以下的更新：
•更新單元 (0, 0) 的數值為20；
•更新單元 (0, 2) 的數值為15；
•更新單元 (1, 1) 的數值為12。
網格的結果如上圖所示。巴勒接著可能會問以下矩形區域裡，全部單元所包含數值的最大公因數：
•對角 (0, 0) 與 (0, 2)：在這個矩形裡的三個整數分別為20、0，以及15，所以它們的最大公因數是5。
•對角 (0, 0) 與 (1, 1)：在這個矩形裡的四個整數分別為20、0、0，以及12，所以它們的最大公因數是4。
現在假設巴勒做了以下的更新：
•更新單元 (0, 1) 的數值為6；
•更新單元 (1, 1) 的數值為14。
新的網格如上圖所示。巴勒接著可能又會問以下矩形區域裡，全部單元所包含數值的最大公因數：
•對角 (0, 0) 與 (0, 2)：現在這個矩形裡的三個整數分別為20、6，以及15，所以它們的最大公因數是1。
•對角 (0, 0) 與 (1, 1)：現在這個矩形裡的四個整數分別為20、6、0，以及14，所以它們的最大公因數是2。
此處巴勒總共進行了 NU = 5 次更新與NQ = 4 次要求計算。
Problem Source
IOI 2013
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~10 | 10 |
| 2 | 11~17 | 27 |
| 3 | 18~26 | 26 |
| 4 | 27~37 | 17 |
| 5 | 38~47 | 20 |