P14039 [PAIO 2025] Cake

Bartosz is celebrating his birthday and receives a rectangular cake with dimensions $N \times M$. As he only likes square-shaped pieces, he decides to cut the entire cake into squares according to a specific method. Each time Bartosz cuts the cake, he slices out the largest possible square so that at least three sides of the square are flush with the sides of the remaining rectangular piece of the cake. This process repeats until the entire cake is divided into nothing but squares. For example, let's say that the rectangle has sizes $5 \times 4$, as shown in the picture below. ::::align{center}  :::: In such example, he will slice out the square $4 \times 4$. After that, he will get a rectangle $1 \times 4$. Therefore, he will slice out a square $1 \times 1$ then for four times. Given the initial cake dimensions $N \times M$, determine the total number of squares Bartosz will obtain using this cutting method. ### Implementation Details You need to implement the following function: ```cpp int32 count_square_cakes(int32 N, int32 M) ``` * $N$: the width of the cake * $M$: the height of the cake * The function should return the number of squares obtained * Note that this function will be called $T$ times per run

N/A

N/A

### Examples Consider the following call `count_square_cakes(5, 4)`. This was explained above, and the answer is 5. Consider the following call `count_square_cakes(6, 6)`. Since the original rectangle is already a square, the answer is 1. Consider the following call `count_square_cakes(11, 2)`. The sizes of the rectangle will be as follows: $11 \times 2$, $9 \times 2$, $7 \times 2$, $5 \times 2$, $3 \times 2$, $1 \times 2$, $1 \times 1$. Therefore, there will be five $2 \times 2$ squares and two $1 \times 1$ squares. 7 in total. Consider the following call `count_square_cakes(12, 6)`. The rectangle will be cut into two $6 \times 6$ squares. Consider the following call `count_square_cakes(18, 5)`. The sizes of the rectangle will be as follows: $18 \times 5$, $13 \times 5$, $8 \times 5$, $3 \times 5$, $3 \times 2$, $1 \times 2$, $1 \times 1$. Therefore, there will be three $5 \times 5$ squares, two $2 \times 2$ squares, and two $1 \times 1$ squares. 7 in total. ### Sample Grader The sample grader reads the input in the following format: * Line 1: One integer $T$ * Next $T$ lines: two integers $N, M$ describing the width and height of the cake. The grader will call the method `count_square_cakes(N, M)` for each of these lines and output the result. ### Constraints * $1 \le T \le 200000$. * $1 \le M \le N \le 10^9$. ### Scoring 1. Subtask 1 (6 points): $M = 1$ 2. Subtask 2 (11 points): $N \le 3$ 3. Subtask 3 (21 points): $N \le 5000$; $T \le 100$ 4. Subtask 4 (17 points): $N \le 5000$ 5. Subtask 5 (27 points): $N \le 100000$; $T \le 100$ 6. Subtask 6 (18 points): No additional constraints