题意简述

有 $n$ 个征兆，第 $i$ 个征兆每 $a_i$ 年发生一次（即在 $a_i, 2a_i, 3a_i, \dots$ 年）。
征兆必须按顺序依次发生：

• 先等第 $1$ 个征兆发生，设发生年份为 $x_1$。
• 然后从 $x_1 + 1$ 年开始等第 $2$ 个征兆，它必须是 $a_2$ 的倍数且严格大于 $x_1$。
• 依此类推。

求第 $n$ 个征兆发生的年份。

---

算法思路

设 $cur$ 表示当前已经发生的最后一个征兆的年份。

初始时没有征兆发生，可以认为 $cur = 0$（实际上第一个征兆会直接取 $a_1$，下面会解释）。

对于第 $i$ 个征兆（周期为 $a_i$），我们需要找到最小的 $k$ 使得：

$$k \cdot a_i > cur$$

即：

$$k = \left\lfloor \frac{cur}{a_i} \right\rfloor + 1 $$

那么该征兆发生的年份为：

$$k \cdot a_i = \left( \left\lfloor \frac{cur}{a_i} \right\rfloor + 1 \right) \cdot a_i $$

---

标程中的简洁写法

标程使用了一行核心代码：

cur += e - cur % e;

我们推导一下为什么这样写等价于上面的计算。

设 $e = a_i$，$cur$ 是上一个征兆的年份。

• $cur \% e$ 是 $cur$ 除以 $e$ 的余数。
• 如果 $cur \% e = r$，那么：

$$cur = q \cdot e + r, \quad 0 \le r < e$$

要找到大于 $cur$ 的最小的 $e$ 的倍数，就是：

$$(q + 1) \cdot e = q \cdot e + e = cur - r + e$$

所以增加的年份为：

$$e - r = e - (cur \% e)$$

因此新的 $cur$ 为：

$$cur_{\text{new}} = cur + (e - cur \% e)$$

---

特殊情况验证

• 若 $cur$ 已经是 $e$ 的倍数（$cur \% e = 0$），则新年份为 $cur + e$，严格大于 $cur$，正确。
• 初始时 $cur = 0$，$0 \% e = 0$，则第一个征兆年份为 $0 + e - 0 = e = a_1$，正确。

---

时间复杂度

每个测试用例 $O(n)$，总复杂度 $O(\sum n) \le 10^5$，完全可行。

---

完整代码（已给出）

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    long long cur = 0;
    for (int e : a) {
        cur += e - cur % e;
    }
    
    cout << cur << endl;
}

int main() {
    int t;
    cin >> t;
    
    for (int i = 1; i <= t; i++) {
        solve();
    }
    
    return 0;
}

---

举例验证

输入：

1
6
3 2 4 5 9 18

执行过程：

步骤	$a_i$	$cur$（更新前）	$cur \% a_i$	$a_i - cur \% a_i$	$cur$（更新后）
1	3	0		3
2		3	1		4
3	4		0	4	8
4	5	8	3	2	10
5	9	10	1	8	18
6	18		0	18	36

输出：$36$，与题目示例一致。

---

总结

这道题的核心是贪心地依次计算每个征兆的最早发生年份，利用取模运算快速跳转到下一个倍数。
公式：

$$cur_{\text{new}} = cur + a_i - (cur \bmod a_i)$$

是解决此类“依次寻找严格大于当前值的最小倍数”问题的常用技巧。