Bazza and Shazza are playing a game. The board is a grid of cells, with
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
Your task is to work out the correct answers.
Example
Suppose
- 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
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()
orcalculate()
.
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 cellQ
: The column of the grid cellK
: 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 rectangleQ
: The column of the top-left cell in the rectangleU
: 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.
Subtasks
Subtask | Points | ||||
---|---|---|---|---|---|
1 | 10 | ||||
2 | 27 | ||||
3 | 26 | ||||
4 | 17 | ||||
5 | 20 |
Comments