Problem Statement
On the table you have a piece of paper. The paper has the shape of a rectangle with the integer dimensions A times B.
You also have a paper cutter. You want to cut your paper into one or more squares. You are going to do that by repeating the following steps:
- If there are some paper squares on the table, remove them from the table.
- If there is no paper left on the table, you are done and the process terminates.
- Make a single straight cut across the paper rectangle on the table in such a way that at least one of the two new pieces is a square.
It can be shown that:
- Whenever we reach step 3, there will always be exactly one paper rectangle on the table.
- In step 3 there will always be a unique way to make the cut. (More precisely, the sizes of the two pieces after we make the cut can always be uniquely determined.)
- For any dimensions of the starting paper rectangle the process will terminate after a finite number of cuts.
Given A and B, count and return the total number of cuts we will make while dividing the A times B rectangle into squares.
Definition
- Class:
- CutAwaySquares
- Method:
- countCuts
- Parameters:
- long, long
- Returns:
- long
- Method signature:
- long countCuts(long A, long B)
- (be sure your method is public)
Notes
- The correct answer will always fit into a signed 64-bit integer variable.
Constraints
- A will be between 1 and 10^18, inclusive.
- B will be between 1 and 10^18, inclusive.
Examples
47
47
Returns: 0
This paper is already a square. We remove it from the table and we are done. There were no cuts.5
10
Returns: 1
We proceed as follows: Step 1: The only paper is a rectangle, we do nothing. Step 2: There is still a paper on the table, we do nothing. Step 3: We cut the 5x10 paper in half. (The cut is through the middle, parallel to the shorter sides.) This divides the paper into two 5x5 squares. Step 1: There are two squares on the table, we remove both of them. Step 2: The table is now empty, so the process ends here.20
2
Returns: 9
In the first round we cut the paper into a 2x2 square and a 18x2 rectangle. Several similar rounds follow. In the last (9th) round in which we still make a cut we cut a 4x2 rectangle into two 2x2 squares.42
22
Returns: 11
After two iterations of making a cut and then removing a square we get the situation from the previous example. Thus, this rectangle needs 2+9 = 11 cuts. When we are done, we'll have a 22x22 square, a 20x20 square, and ten 2x2 squares.20000000000000
2000000000000
Returns: 9
Watch out for integer overflow, A and B can be large. (This example is just a scaled version of Example 2, so it also requires 9 cuts.)