Problem : 292 - Game

Problem Statistics

Solved Member: 32　　Submission: 491　　User Tried: 36

Statement:

巴勒與夏拉正在玩一個遊戲。遊戲盤是一個由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）前，最多將進行N_U + N_Q 個動作（更新N_U次及要求計算N_Q 次）。

你的任務是算出正確的答案。

Input:Output:

第一行有三個數字R C N，表示遊戲盤大小與巴勒的動作次數。

接下來 N 行，依照動作發生的順序，一個動作一行，表示動作的那一行必須是以下其中一種格式：

　•1 P Q K，表示更新(P,Q)的值為K。
　•2 P Q U V，表示查詢以(P, Q) 與 (U, V)為兩對角所構成的矩形內所有元素的最大公因數。

限制：
　•1 ≤ R, C ≤ 10⁹
　•0 ≤ K ≤ 10¹⁸，K 是巴勒放置於網格單元的任何整數值。

對於每個查詢，輸出一個數字表示答案，每個數字佔一行。

Sample Input:Sample Output:

2 3 9
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

5
4
1
2

HINT:

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 次要求計算。

Source:

IOI 2013

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	3000ms	235520kb
1-1	3000ms	235520kb	10
1-2	3000ms	235520kb
1-3	3000ms	235520kb
1-4	3000ms	235520kb
1-5	3000ms	235520kb
1-6	3000ms	235520kb
1-7	3000ms	235520kb
1-8	3000ms	235520kb
1-9	3000ms	235520kb
1-10	3000ms	235520kb
1-11	3000ms	235520kb
2-1	10000ms	235520kb	27
2-2	10000ms	235520kb
2-3	10000ms	235520kb
2-4	10000ms	235520kb
2-5	10000ms	235520kb
2-6	10000ms	235520kb
2-7	10000ms	235520kb
3-1	10000ms	235520kb	26
3-2	10000ms	235520kb
3-3	10000ms	235520kb
3-4	10000ms	235520kb
3-5	10000ms	235520kb
3-6	10000ms	235520kb
3-7	10000ms	235520kb
3-8	10000ms	235520kb
3-9	10000ms	235520kb
4-1	10000ms	235520kb	17
4-2	10000ms	235520kb
4-3	13000ms	235520kb
4-4	13000ms	235520kb
4-5	10000ms	235520kb
4-6	10000ms	235520kb
4-7	10000ms	235520kb
4-8	10000ms	235520kb
4-9	10000ms	235520kb
4-10	10000ms	235520kb
4-11	10000ms	235520kb
4-12	10000ms	235520kb
5-1	13000ms	235520kb	20
5-2	13000ms	235520kb
5-3	15000ms	235520kb
5-4	13000ms	235520kb
5-5	13000ms	235520kb
5-6	13000ms	235520kb
5-7	13000ms	235520kb
5-8	13000ms	235520kb
5-9	13000ms	235520kb
5-10	13000ms	235520kb