AT_abc231_e [ABC231E] Minimal payments

题目描述

在 Atcoder 王国中，使用 $N$ 种面额的硬币，分别为 $A_1$ 元、$A_2$ 元、$\ldots$、$A_N$ 元。
其中 $1 = A_1 < \ldots < A_N$，并且对于所有 $1 \leq i \leq N-1$，$A_{i+1}$ 都是 $A_i$ 的倍数。

现在你需要用这些硬币支付 $X$ 元。你可以支付超过 $X$ 元，然后用硬币找零。请问，支付时所用硬币枚数与找零时所用硬币枚数之和的最小值是多少？

更准确地说，对于任意 $Y \geq X$，你需要用最少的硬币表示 $Y$ 元和 $Y-X$ 元，求这两者所用硬币数之和的最小值。

输入格式

输入通过标准输入给出，格式如下：

$N$ $X$ $A_1$ $\ldots$ $A_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 87
1 10 100

输出 #1

5

输入输出样例 #2

输入 #2

2 49
1 7

输出 #2

7

输入输出样例 #3

输入 #3

10 123456789012345678
1 100 10000 1000000 100000000 10000000000 1000000000000 100000000000000 10000000000000000 1000000000000000000

输出 #3

233

说明/提示

限制条件

• 输入中的所有值均为整数。
• $1 \leq N \leq 60$
• $1 = A_1 < \ldots < A_N \leq 10^{18}$
• 对于所有 $1 \leq i \leq N-1$，$A_{i+1}$ 是 $A_i$ 的倍数。
• $1 \leq X \leq 10^{18}$

样例解释 1

用 $1$ 枚 $100$ 元硬币支付，然后用 $1$ 枚 $10$ 元硬币和 $3$ 枚 $1$ 元硬币找零，总共需要 $5$ 枚硬币。

样例解释 2

直接用 $7$ 枚 $7$ 元硬币支付是最优的。

由 ChatGPT 4.1 翻译