P3951 [NOIP 2017 Senior] Xiaokai's Doubt

NOIP 2017 Senior D1T1.

Xiaokai has two coin denominations, both positive integers and coprime. He has infinitely many coins of each denomination. Without making change, using only these two denominations, there are some item prices he cannot pay exactly. Now Xiaokai wants to know: among the prices that cannot be paid exactly, what is the most expensive price? Note: The input guarantees that there exists an item that Xiaokai cannot pay exactly.

Two positive integers $a$ and $b$, separated by a single space, representing the denominations of Xiaokai's coins.

A single positive integer $N$, the most expensive item price that cannot be paid exactly without making change.

[Explanation for Sample 1] Xiaokai has infinitely many coins with denominations $3$ and $7$. Without making change, he cannot pay exactly for items priced $1, 2, 4, 5, 8, 11$. Among them, the most expensive price is $11$. Every price greater than $11$ can be paid, for example: $12 = 3 \times 4 + 7 \times 0$； $13 = 3 \times 2 + 7 \times 1$； $14 = 3 \times 0 + 7 \times 2$； $15 = 3 \times 5 + 7 \times 0$。 Constraints For $30\%$ of the testdata: $1 \le a,b \le 50$。 For $60\%$ of the testdata: $1 \le a,b \le 10^4$。 For $100\%$ of the testdata: $1 \le a,b \le 10^9$。 Translated by ChatGPT 5