P2236 [HNOI2002] Lottery

A set of lottery tickets is issued in a certain place. Each ticket displays the $M$ natural numbers from $1$ to $M$. A player may circle any $N$ distinct numbers among these $M$ numbers. Each player can buy only one ticket, and different players choose different sets. Each draw picks two natural numbers $X$ and $Y$. If, on someone's ticket, the sum of the reciprocals of the $N$ selected natural numbers is exactly equal to $\dfrac{X}{Y}$, then they will receive a souvenir. Given the draw result $X$ and $Y$, determine how many souvenirs must be prepared to ensure all winners can be awarded.

The input contains exactly one line with four integers $N$, $M$, $X$, $Y$ separated by spaces.

Output one line with the required number of souvenirs.

$1 \leq X, Y \leq 100$, $1 \leq N \leq 10$, $1 \leq M \leq 50$. The input guarantees the output does not exceed $10^5$. Translated by ChatGPT 5