🔗 Intact Squares

There is a rectangular sheet of paper with a width of W cm and a height of H cm. The paper has lines drawn on it in a grid pattern, parallel to the width and height directions, and every grid cell is 1 cm x 1 cm in size. This paper was meant to be cut along the grid lines into 1 cm × 1 cm squares, but someone cut it along the direction connecting two diagonal corners. As a result, the rectangular sheet is now currently divided into 2 right triangles of equal size. Since a new sheet of paper cannot be obtained, it was decided to use only as much as can be cut into 1 cm × 1 cm squares parallel to the original paper's width and height directions.

Given the width W and height H, complete the solution function that finds the number of squares that can be used.

• W, H: natural numbers no greater than 100 million

Example #1

If you cut a rectangle with a width of 8 and a height of 12 diagonally, a total of 16 squares become unusable. Since the original rectangle could produce 96 squares, the function returns 96 - 16 = 80.

Since there's no direct hint, let's infer a pattern from the given information.

At certain points, the diagonal line crosses exactly through a grid intersection, and these points are marked with blue circles in the picture above.

The coordinates of the blue circles are (2, 3), (4, 6), (6, 8), and (8, 12).

In other words, starting from (2, 3), the coordinate values increase by exactly 2 each time, and the same pattern is observed a total of 4 times.

(8, 12) -> (2, 3) can be obtained by dividing each coordinate value by 4, where 4 here is the greatest common divisor of w and h, which are 8 and 12.

So, by properly combining w, h, and the greatest common divisor of w and h, we can derive a general formula.

Having found the pattern, we just need to derive the general formula for the rectangle excluded by this pattern.

Since the pattern repeats as many times as the greatest common divisor, we can infer the general formula as follows.

Number of usable rectangles = total number of rectangles - (number of rectangles excluded per pattern * greatest common divisor)

Analyzing each pattern makes it easy to determine the number of rectangles excluded per pattern.

1. A (2, 3)-sized rectangle. 4 rectangles are affected.
2. A (5, 2)-sized rectangle. 6 rectangles are affected.
3. A (1, 1)-sized rectangle. 1 rectangle is affected.

Based on this pattern, the number of rectangles excluded per pattern turns out to be width + height - 1.

So the final general formula is as follows.

(w * h) - (((w / gcd) + (h / gcd) - 1) * gcd).

Since the return value is long, be careful not to return an int.

JAVA
/**
 * Intact Squares class
 *
 * @author RWB
 * @since 2021.12.26 Sun 22:31:31
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param w: [int] width
	 * @param h: [int] height
	 *
	 * @return [int] answer
	 */
	public long solution(int w, int h)
	{
		long ref = gcd(w, h);
		
		return ((long) w * h) - (((w / ref) + (h / ref) - 1) * ref);
	}
	
	/**
	 * Method that returns the result of the Euclidean algorithm
	 *
	 * @param n: [int] integer 1
	 * @param m: [int] integer 2
	 *
	 * @return [int] greatest common divisor
	 */
	private int gcd(int n, int m)
	{
		while (m != 0)
		{
			int r = n % m;
			
			n = m;
			m = r;
		}
		
		return n;
	}
}