从逐次减法到高效除法

题目描述：

给定初始值 N，以及 M 种操作，每种操作 (a, b)，表示每次操作必须满足 N >= a，然后 N 会减少 b。要求计算最多可以执行多少次操作，并更新 N。

---

思路与推导：

1. 操作描述：
   每个操作 (a, b)，表示：

   • 只有当 N >= a 时，才能进行操作。
   • 每次操作会将 N 减去 b，直到无法继续执行为止。

2. 最大操作次数的推导：
   假设对于某个操作 a 和 b，我们希望计算最多可以执行多少次该操作。

   由于每次操作将 N 减少 b，为了保证 N 始终大于等于 a，我们可以得到以下条件：

   $$N - t \cdot b \geq a$$

   其中 t 为最大执行次数。由此可以得到：

   $$t \leq \frac{N - a}{b}$$

   这意味着最多可以进行 $t = \left\lfloor \frac{N - a}{b} \right\rfloor$ 次操作。

   为什么要加 1？

   • 因为N在减了t次之后还是大于或等于a的 $$N - t \cdot b \geq a$$ 还可以再进行一次操作,这次减了b了之后,N小于a,不会再进行下一次(a,b)操作了

   所以，最终的最大操作次数是：

   $$t = \left\lfloor \frac{N - a}{b} \right\rfloor + 1$$

3. 更新 N：
   每次操作执行 t 次后，N 会减少 t * b。更新后的 N 为：

   $$N = N - t \cdot b$$

   继续进行下一个操作，直到遍历所有操作。

---

示例：

输入：

100 2
20 3
50 5

输出：

27

解释：

1. 第一个操作：a = 20, b = 3，计算 (100 - 20) / 3 + 1 = 27，执行 27 次，更新 N = 100 - 27 * 3 = 19。
2. 第二个操作：a = 50, b = 5，由于 N = 19 小于 50，跳过该操作。
3. 最终输出 cnt = 27。

---

总结：

通过优化循环，使用数学公式一次性计算每个操作的最大执行次数，避免了逐次减法，从而提高了程序效率。核心考察了通过数学推导解决动态问题和优化计算时间的能力。