核聚变反应强度

算法一

对于 $n=1$ 的数据，就是求一个数次大的约数。

众所周知一个数$x$的约数是成对出现的（$d$、$\frac{x}{d}$），其中总有一个不超过$\sqrt{x}$。所以从$1$到$\sqrt{a_1}$地枚举$d$就能找出所有$a_1$的约数了。排序输出次大的即可。

复杂度：$O(\sqrt{a})$

算法二

先找出$a_1$的所有约数，然后枚举$i$，$\text{sgcd}(a_1,a_i)$显然也是$a_1$的约数，所以枚举$a_1$的所有约数，找到是$a_i$约数的次大的即可。

复杂度：$O(n\sqrt{a})$

算法三

考虑分解质因子后：

$a=p_1^{x_1}p_2^{x_2}...p_m^{x_m}$

$b=p_1^{y_1}p_2^{y_2}...p_m^{y_m}$

则：$\gcd(a,b)=p_1^{\min(x_1,y_1)}p_2^{\min(x_2,y_2)}...p_m^{\min(x_m,y_m)}$

我们发现，$a$和$b$的公约数都一定是$\gcd(a,b)$的约数。那么为了得到次大公约数，只需求出$\gcd(a,b)$，再除去一个最小的公共质因子即可。

对$a_1$用$O(\sqrt{a_1})$的时间分解得到$O(\log(a_1))$个质因数，每次对于$a_i$，先求出$g=\gcd(a_1,a_i)$，然后枚举$a_1$的每个质因数，找到最小的能整除$g$那个，设其为$p$，$g/p$即为所求。（不存在则为输出$-1$）

复杂度：$O(\sqrt{a}+n \log(a))$

一个骗分算法

考虑算法二，我们预先对 $a_1$ 的约数们排好序，然后枚举 $i$，从约数表里每次二分到 $\gcd(a_1,a_i)$所在位置，再往前枚举，找到第一个能整除$a_i$的即为次大公约数。

虽然复杂度不靠谱，但是对于$a_i \leq 10^{12}$的范围实际运行速度十分优秀。需要构造针对的数据才能卡住。

还有另一个骗分算法，求出 $\gcd$ 然后暴力枚举最小质因子。好多人写这个啊……你们都没意识到复杂度不对么……放你们一马给了 80 分。

（有这种闲心的为啥不写正解啊，你们考虑过 maker 的感受吗！QAQ）

铀仓库

算法一

我们先来证明几个显然的结论。

结论一：小O的行动一定是，每次看准一个箱子，从$s$跑过去拿起来，然后直接搬回$s$。

首先，小O一定不会把一个箱子搬到离$s$更远的地方。其次我们考虑，如果小O进行了这样的动作：从$a$搬到$b$、从$c$搬到$d$，其中$a < b < c < d < s$，那么等价于从$a$搬到$d$，从$c$搬到$b$，显然干了多余的事。

结论二：起始位置$s$一定有箱子。

考虑确定了$s$，一定是搬来前若干近的箱子，也就一定是连续的一段，所耗时间为距离和的两倍。我们知道，给定数轴上若干个点，选一个坐标最小化每个点到它的距离和，那么一定是选这些点坐标中的中位数（调整法可证）。

说了一大堆废话，我们得到一个暴力做法。枚举$s$，每次拿来一个最近的即可。

复杂度：$O(n^2T)$

算法二

枚举$s$，由于是取前若干近的过来，我们二分取的最远的在哪。如果$x_i=i$那么直接可以$O(1)$确定左右端点，否则我们需要再一次二分确定左右端点。

复杂度：$O(n \log n \log X)$，$X$表示坐标范围。

算法三

先二分答案，于是问题变成了：求叠到$K$个箱子所需的最短时间。

由于取的一定是连续的一段，设其为$[l,r]$，若$a_i=1$，我们直接从左到右枚举$s$，此时由于左边的越来越远，右边的越来越近，$l、r$一定是非降的。所以，每次$s$右移的时候，判断$r+1$处是否比$l$近，如果是就一直替换，直到不是为止。

移动左右端点的同时顺便维护一下距离和就好了。

这样的复杂度是$O(n+Σa_i)$的，还是不能通过全部数据。

加一个小优化就好了。把每个位置的$a_i$个箱子想象成横着紧贴成一排，称为一组箱子，那么每次我们移动左右端点$l、r$的时候，事实上是干了很多重复的事情的。

如果$l$、$r$所在箱子组都不变，那么会一直进行替换，直到某个端点换组。所以在每次替换的时候，直接加速到某个端点换组的时刻即可。

复杂度：$O(n \log X)$

链式反应

算法一

按照题意进行爆搜，可以通过第一个测试点获得 10 分。

算法二

我们得思考一下这题题意到底是啥意思。其实说，一棵有标号的树，编号满足堆的性质，对于儿子方向每个结点有两条红色边，$c$ 条黄色边，$c$ 属于集合 $A$，统计方案数。

所以我们用 $f[n]$ 表示 $n$ 个结点的这个样子的树的方案数。然后要么 $1$ 号点没有进行核裂变，此时必有 $n = 1$ 且 $f[n] = 1$。要么 $1$ 号结点进行了核裂变，此时我们枚举两个中子打中的结点的子树的大小 $j, k$，剩下的就是被破坏死光打中的，于是要满足 $i - 1 - j - k \in A$。然后考虑两个中子打中的结点的子树，我们先选出它们的编号，方案数是 $\binom{i - 1}{j} \cdot \binom{i - 1 - j}{k}$，然后我们就可以安全地把这两棵子树的结点都重标号，方案数自然是 $f[j]$ 和 $f[k]$。所以我们把这些杂八事综合起来就得到了一个简单的DP：$f[i] = \sum_{j}{\sum_{k}{\binom{i - 1}{j} \cdot \binom{i - 1 - j}{k} \cdot f[j] \cdot f[k]}}$。这里的 $j, k$ 要满足 $i - 1 - j - k \in A$。直接暴力递推就得到了一个 $O(n^3)$ 的算法。

什么，过不了样例？当然过不了样例了，因为有重复计数。那两个中子是等价的，一个方案自然会被统计了两遍，只要把 DP 方程除以 $2$ 就好了。

可以通过前 $4$ 个测试点获得 40 分。

算法三

其实只要在算法二基础上优化就行了。我们仔细观察式子：$\binom{i - 1}{j} \cdot \binom{i - 1 - j}{k} = \frac{(i - 1)!}{j! k! (i - j - k - 1)!}$。有四个部分，第一个只跟 $i$ 有关，第二个只跟 $j$ 有关，第三个只跟 $k$ 有关，第四个只跟 $i - j - k - 1$ 有关。所以我们可以递推一个 $g[i] = \sum_{k}{\frac{f[k]}{k!} \frac{f[i - k]}{(i - k)!}}$。然后递推 $f[i]$ 时我们枚举 $j + k$ 的和 $s$，那么直接读取 $g[s]$ 的值，然后剩下的部分就是一些跟 $i$ 和 $s$ 有关的了。

好像说得挺意识流的，具体就是：$f[i] = \frac{1}{2}\sum_{s}{g[s] \cdot \frac{(i - 1)!}{(i - s - 1)!}}$。$s$ 要满足 $i - s - 1 \in A$。

可以通过前 $6$ 个测试点获得 60 分。

算法四

再观察一下式子，搞个数组 $a$，其中如果 $i \in A$ 则 $a_i = \frac{1}{i!}$，否则为 $0$。然后原递推式的右边的第 $i$ 项其实就是 $g$ 跟 $a$ 的卷积的第 $i - 1$ 项然后再乘以 $(i - 1)!$。然后其实 $g$ 本身也是个卷积，就是 $\frac{f[i]}{i!}$ 这个数列的平方。

我们可以使用分治。每次分治一个区间 $[l, r]$，我们找出中点 $m$，然后递归 $[l, m]$，然后求出 $[l, m]$ 对 $[m + 1, r]$ 的贡献，再递归右边。

考虑左边对右边的贡献，“$\binom{i - 1}{j} \cdot \binom{i - 1 - j}{k} \cdot f[j] \cdot f[k]$” 中，左边可能作为 $f[j]$ 也可能作为 $f[k]$ 出现，也可能都出现。我们只要考虑这几种情况然后分别进行 FFT 就行了。看起来要和整个 $a$ 或者 $f$ 进行卷积？其实不然，只用取出一个长度为分治时的区间的长度的前缀就可以了。

时间复杂度 $O(n \log^2 n)$。可以通过前 $9$ 个测试点获得 90 分。常数小的话应该能过。

算法五

以下内容需要一点微积分知识……如果是微积分恐惧症……您还是看算法四加卡常数吧～我还是很良心的没让所有人都非得用算法五才能AC～

嗯，既然都发现是卷积了，那么肯定少不了生成函数。我们记 $\frac{f[i]}{i!}$ 的生成函数为 $x(t)$，$a_i$ 的生成函数为 $a(t)$，那么生成函数就要满足：$x'(t) = \frac{1}{2}a(t)x^2(t) + 1$。

拨一下 mathematica 就会发现它解不出来这个微分方程，所以只有自力更生了。

首先科普下一般来说应该怎么解一个多项式方程（更严谨地说这里应该是形式幂级数）。假设 $x(t)$ 满足 $f(x(t)) = 0$，那么我们先求出 $0$ 次项的系数，然后每次倍增。也就是说每次我们有一个多项式 $x_n$ 满足 $x_n$ 和 $x$ 的前 $n$ 项系数是一样的，我们记为 $x \equiv x_n \pmod{t^n}$，然后我们要求出 $x_{2n}$ 满足 $x \equiv x_{2n} \pmod{t^{2n}}$。使用泰勒展开可以得到:

\begin{equation} 0 = f(x_{2n}) = f(x_n) + f'(x_{n}) (x_{2n} - x_n) + \frac{1}{2} f''(x_{n}) (x_{2n} - x_n)^2 + \dots \end{equation}

注意到如果只考虑前 $2n$ 项，那么就可以去掉二次项及之后的项然后解出：

\begin{equation} x_{2n} \equiv x_n - \frac{f(x_n)}{f'(x_n)} \pmod{t^{2n}} \end{equation}

由于 $T(n) = T(n / 2) + O(n \log n)$ 解出来是 $T(n) = O(n \log n)$，所以只要能足够快地把 $x$ 带入 $f(x)$，那么就能 $O(n \log n)$ 解方程。（当然需要 FFT 做多项式乘法）

什么这里有个除法？我们可以利用牛顿迭代求出一个形式幂级数的乘法逆元，于是就能做除法了。

于是微分方程也可以如法炮制，假设有个这样的一阶微分方程：

\begin{equation} \frac{d}{dt}x = f(x) \end{equation}

我们还是老样子：

\begin{eqnarray} \frac{d}{dt}x_{2n} & \equiv & f(x_n) + f'(x_n) \cdot (x_{2n} - x_n) \pmod{t^{2n}}\\\\ & \equiv & f(x_n) + f'(x_n) \cdot x_{2n} - f'(x_n) \cdot x_n \pmod{t^{2n}} \end{eqnarray}

所以问题变成了这玩意儿怎么解……而这玩意儿其实很好解……我们两边同时乘以 $e^{-\int{f'(x_n) dt}}$（囧……由于公式嵌套过多，排版已经开始混乱了），记作 $r$：

\begin{eqnarray} \frac{d}{dt}x_{2n}\cdot r & \equiv & (f(x_n) - f'(x_n) \cdot x_n) \cdot r + f'(x_n) \cdot x_{2n} \cdot r \pmod{t^{2n}}\\\\ \frac{d}{dt}(x_{2n}\cdot r) & \equiv & (f(x_n) - f'(x_n) \cdot x_n) \cdot r \pmod{t^{2n}} \end{eqnarray}

然后只要把右边积分再除以 $r$ 就行了。

注意到虽然人类无法方便地给任意函数积分，但是给多项式求导和求积分简直易如反掌。所以唯一的难点在于 $r$ 怎么求。

好吧其实我几个月前 YY 到这里直接就弃疗了，后来翻了翻论文，知道了怎么求 $e^x$。由于 $e^x$ 的反函数是 $\ln(x)$ 而 $\ln(x)$ 对 $t$ 的导数是 $\frac{x'}{x}$，所以 $\ln(x)$ 可以快速求，然后我们就可以进行牛顿迭代求 $\ln(x)$ 的反函数得到 $e^x$。

对于本题，$f(x) = \frac{1}{2} ax^2 + 1$，然后无脑使用上述方法就行了。

本来还想当一个原创算法呢……结果后来发现国外论文上早就有了……果然我还是太naive……

时间复杂度 $O(n \log n)$。可以通过所有测试点获得 100 分。

形式幂级数真是个优美的东西啊，很多在实数域内有条件收敛的算法，到形式幂级数上就一定收敛了，我不得不表示赞叹。