Laser Reflection on a Rectangular Mirror

A teacher once told Little Ben that the angle of reflection is equal to the angle of incidence. He then gave him the following problem:

Given a rectangle with a length-to-width ratio of N:M, a laser beam is fired from the top left corner with an angle \(\zeta\) (where \(0 \le \zeta \le 90\)) relative to the side of length N. It is known that \(\cot \zeta = \frac{A}{B}\) (i.e. \(\tan \zeta = \frac{B}{A}\)). Using the law of reflection, determine the minimum number of reflections needed so that the beam eventually hits one of the four corners of the rectangle.

Note: The law of reflection states that the angle of incidence equals the angle of reflection. By using the method of unfolding the rectangle, the problem can be transformed into finding the smallest positive integers \(k\) and \(l\) such that the beam, travelling in the direction \((A, B)\), reaches the point \((k \cdot N, l \cdot M)\). The number of reflections is then \(k + l - 2\).

If we let \(d = \gcd(M \cdot A, N \cdot B)\), the minimal integers can be expressed as:

\[ k = \frac{M \cdot A}{d}, \quad l = \frac{N \cdot B}{d}, \quad \text{and the answer is } k + l - 2. \]

inputFormat

The input consists of a single line with four positive integers separated by spaces:

• N: the length ratio component of the rectangle
• M: the width ratio component of the rectangle
• A and B: two positive integers such that \(\cot \zeta = \frac{A}{B}\)

It is guaranteed that the given values yield a valid physical scenario (i.e. \(0 < \zeta < 90\)).

outputFormat

Output a single integer, the minimum number of reflections required for the laser beam to hit one of the four corners of the rectangle.

sample

3 2 1 1

3