Maximize Unchanged Trees

There are initially n willow trees planted in a row with a constant spacing x between adjacent trees. The first tree’s position (the starting point) is fixed and cannot be changed.

You need to rearrange or remove some trees so that the final configuration (which must start at the same point as the original) has every two consecutive trees exactly y apart where y > x.

The allowed operations are:

1. Remove a tree: Delete a tree at its current position.
2. Transplant a tree: Move a tree from one position to any other position.

You are not allowed to add a new tree.

Your goal is to achieve the desired configuration while maximizing the number of trees that remain at their original positions.

A tree originally at position a + i*x (where i is the index starting from 0) can remain unchanged if and only if its coordinate equals one of the final positions: a, a+y, a+2y, .... This equality holds if and only if
\(a + i*x = a + j*y\) for some integer j, i.e., \(i*x = j*y\).

Let \(d = \gcd(x, y)\), and write \(x = d*x_1\) and \(y = d*y_1\). Since \(\gcd(x_1, y_1)=1\), the equation \(i*x_1 = j*y_1\) has an integer solution for j if and only if \(y_1\) divides \(i\). Therefore, the number of trees that can remain unchanged is the number of indices in \([0, n-1]\) that are multiples of \(y_1\), which is given by:

[ \text{res} = \left\lfloor \frac{n-1}{y_1} \right\rfloor + 1. ]

Print the maximum count of trees that can remain in their original positions.

inputFormat

The input consists of a single line containing three positive integers n, x, and y separated by spaces:

• n: the total number of trees.
• x: the original spacing between consecutive trees.
• y: the required spacing between consecutive trees in the final configuration (with y > x).

outputFormat

Output a single integer, the maximum number of trees that can remain at their original positions, while achieving a configuration in which the spacing between any two consecutive trees is exactly y.

sample

5 2 6

2