Maximize Unmoved Willow Trees

There are n willow trees originally planted in a line. The trees are initially placed so that the distance between consecutive trees is x. That is, the trees are located at positions

$$0,\; x,\; 2x,\; \dots,\; (n-1)x.$$

Now, you want to rearrange the trees so that, while keeping the starting tree (at position 0) unchanged, the distance between any two consecutive trees becomes y (with \( y > x \)). That is, after rearrangement the trees will be at positions

$$0,\; y,\; 2y,\; \dots,\; (n-1)y.$$

You are allowed to perform the following operation:

• Transplant a tree: Move a tree from its current position to another position.

Since transplanting a tree requires effort, you wish to keep as many trees as possible in their original positions. In other words, you want to achieve the new configuration by moving as few trees as possible.

Find the maximum number of trees that can remain unmoved so that the positions of the trees become exactly \(0,\; y,\; 2y,\; \dots,\; (n-1)y\) with the starting tree fixed at 0.

Hint: A tree originally at position \(i\cdot x\) will not need to be moved if and only if \(i\cdot x\) is one of the new positions, i.e., \(i\cdot x = j\cdot y\) for some integer \(j\). Using the fact that \(\gcd(x,y)\) is the greatest common divisor of \(x\) and \(y\), you can show that the answer is given by:

$$\text{answer} = \left\lfloor \frac{(n-1)\cdot \gcd(x,y)}{y} \right\rfloor + 1. $$

inputFormat

The input consists of a single line containing three integers n, x, and y (y > x), where:

• n (1 ≤ n ≤ 10⁹) is the number of trees.
• x (1 ≤ x ≤ 10⁹) is the initial interval between consecutive trees.
• y (x < y ≤ 10⁹) is the desired interval between consecutive trees.

It is guaranteed that the numbers are such that the answer will always be a non-negative integer.

outputFormat

Output a single integer denoting the maximum number of trees that can remain in their original positions after rearranging the trees.

Recall that the formula for the answer is:

$$\text{answer} = \left\lfloor \frac{(n-1)\cdot \gcd(x,y)}{y} \right\rfloor + 1. $$

sample

5 2 3

2