No.176

$$Ax + By = k \ (x, y \geq 0, k \geq T)$$

である最小の $k$ を求める問題である.

$y$ を $0$ から順に探索する. 探索範囲は, $0 \leq y \leq \min({\rm lcm}(A, B), \lceil T/B \rceil)$ である. これは, $y = {\rm lcm}(A, B) + k$ のときは $y$ を $k$ 枚にしてその分を $A$ に振り分けたときと合計金額が変わらないからである.