UOJ Round #3
A. 核聚变反应强度
20
$n = 1, a_i \le 10^9$
即求 $a_1$ 的次大约数。
众所周知，一个数 $x$ 的约数总是形如 $(d, \frac{x}{d})$ 地成对出现。
从 $1$ 到 $\sqrt a_1$ 枚举 $d$ 得到 $x$ 的所有约数，排序输出次大值。
时间复杂度 $\mathcal O(\sqrt a)$。
60
$n \le 10^4, a_i \le 10^9$
枚举每个 $i$ 依次考虑。
$\text{sgcd}(a_1, a_i)$ 同时是 $a_1, a_i$ 的约数，枚举 $a_1$ 的所有约数，找到是 $a_i$ 约数的次大值。
时间复杂度 $\mathcal O(n \sqrt a)$。
100（骗分）
$\text{sgcd}(a_1, a_i) \lt \gcd(a_1, a_i)$，先求出 $d = \gcd(a_1, a_i)$，只枚举 $a_1$ 约数中小于 $d$ 的即可。
复杂度不靠谱，但是对于 $a_i \le 10^{12}$ 的范围实际运行速度十分优秀，需要构造针对的数据才能卡住。
100
$n \le 10^5, a_i \le 10^{12}$
考虑分解质因子。
\[\begin{aligned} a & = p_1^{x_1} p_2^{x_2} \cdots p_m^{x_m} \\ b & = p_1^{y_1} p_2^{y_2} \cdots p_m^{y_m} \\ \gcd(a, b) & = p_1^{\min(x_1, y_1)} p_2^{\min(x_2, y_2)} \cdots p_m^{\min(x_m, y_m)} \end{aligned}\]$a, b$ 的公约数一定是 $\gcd(a, b)$ 的约数，将 $\gcd(a, b)$ 除去其最小质因子即可得到 $\text{sgcd}(a, b)$。
对 $a_1$ 使用 $\mathcal O(\sqrt a_1)$ 的时间分解得到 $\mathcal O(\log a_1)$ 个质因数。
对于每个 $a_i$，求出 $d = \gcd(a_1, a_i)$，在 $a_1$ 的质因数种找到最小的 $p$ 使得 $p$ 整除 $d$，$\frac{d}{p}$ 即为所求。
时间复杂度 $\mathcal O(\sqrt a + n \log a)$。
B. 铀仓库
30
$n \le 100, t \le 1000$
小 O 的行动一定是，每次看准一个箱子，从 $s$ 跑过去拿起来，然后直接搬回 $s$，且起始位置 $s$ 一定有箱子。
于是枚举 $s$，每次搬最近的箱子。
时间复杂度 $\mathcal O(n^2 t)$。
80
$n \le 10^5, t \le 10^{18}$
仍然枚举 $s$，搬前若干近的箱子，可以二分最远距离。
若有 $x_i = i$ 可以 $\mathcal O(1)$ 确定左右端点，否则需要再次二分确定左右端点。
时间复杂度 $\mathcal O(n \log n \log x)$。
100
$n \le 5 \times 10^5, t \times 10^{18}$
二分答案，检查即为求叠 $mid$ 个箱子的最短时间。
搬的箱子一定是连续的一段，记其为 $[l, r]$。
从左到右枚举 $s$，$l, r$ 一定单调不降，双指针维护一下。
时间复杂度 $\mathcal O(n \log x)$
C. 链式反应
10
$n \le 8$
暴搜。
40
\[f[i] = \frac{\sum_j \sum_k \binom{i - 1}{j} \cdot \binom{i - 1 - j}{k} \cdot f[j] \cdot f[k]}{2}\]其中 $i - 1 - j - k \in A$。
时间复杂度 $\mathcal O(n^3)$。