## IOI '13 P6 - Game

View as PDF

Points: 25 (partial)
Time limit: 5.5s
Memory limit: 230M

Problem types
Allowed languages
C++

Bazza and Shazza are playing a game. The board is a grid of cells, with rows number , and columns numbered . We let denote the cell in row and column . Each cell contains a non-negative integer, and at the beginning of the game all of these integers are zero.

The game proceeds as follows. At any time, Bazza may either:

• update a cell , by assigning the integer that it contains;
• ask Shazza to calculate the greatest common divisor (GCD) of all integers within a rectangular block of cells, with opposite corners and inclusive.

Bazza will take actions (updating cells times and asking question times) before he gets bored and goes outside to play cricket.

#### Example

Suppose and , and Bazza begins with the following updates:

• Update cell to ;
• Update cell to ;
• Update cell to .

The resulting grid is shown in the picture above. Bazza might then ask for GCDs in the following rectangles:

• Opposite corners and : The three integers in this rectangle are , and , and their GCD is .
• Opposite corners and : The four integers in this rectangle are , , , and , and their GCD is .

Now suppose Bazza makes the following updates:

• Update cell to ;
• Update cell to .

The new grid is shown in the picture above. Bazza might then ask for GCDs in the following rectangles again:

• Opposite corners and : Now the three integers in this rectangle are , and , and their GCD is .
• Opposite corners and : Now the four integers in this rectangle are , , and , and their GCD is .

Here Bazza has performed updates and questions.

#### Implementation

You should submit a file implementing the procedures init() and update() and the function calculate(), and described below.

Your procedure: init()

C/C++

void init(int R, int C);


Pascal

procedure init(R, C : LongInt);


Description

Your submission must implement this procedure.

This procedure give you the initial size of the grid, and allows you to initialise any global variables and data structures. It will only be called once, before any calls to update() or calculate().

Parameters

• R: The number of rows.
• C: The number of columns.

Your Procedure: update()

C/C++

void update(int P, int Q, long long K);


Pascal

procedure update(P, Q : LongInt; K : Int64);


Description

Your submission must implement this procedure.

This procedure will be called when Bazza assigns the number in some grid cell.

Parameters

• P: The row of the grid cell
• Q: The column of the grid cell
• K: The new integer in this grid cell . May be the same as the current value.

Your Function: calculate()

C/C++

long long calculate(int P, int Q, int U, int V);


Pascal

function calculate(P, Q, U, V : LongInt) : Int64;


Description

Your submission must implement this function.

This function should calculate the greatest common divisor of all integers in the rectangle with opposite corners and . This range is inclusive, i.e., the cells and are included in the rectangle.

If all the integers in this rectangle are zero, then this function should return zero also.

Parameters

• P: The row of the top-left cell in the rectangle
• Q: The column of the top-left cell in the rectangle
• U: The row of the bottom-right cell in the rectangle .
• V: The column of the bottom-right cell in the rectangle
• Returns: The GCD of all integers in the rectangle, or if all those integers are zero.

#### Sample Session

The following session describes the example above:

Function Call Returns
init(2, 3)
update(0, 0, 20)
update(0, 2, 15)
update(1, 1, 12)
calculate(0, 0, 0, 2) 5
calculate(0, 0, 1, 1) 4
update(0, 1, 6)
update(1, 1, 14)
calculate(0, 0, 0, 2) 1
calculate(0, 0, 1, 1) 2

#### Constraints

• , where is any integer that Bazza places in a grid cell.