2025 长训第五周 (1022 to 1029)

1022【模拟赛 #13】

一个数的本质不同质因子只有 $O (\log x)$ 个左右，然后由于次小公因数等于最大公因数除以其最小质因子，而其最小质因子一定是 $a_{1}$ 的最小质因子，因此先分解 $a_{1}$ 之后枚举每个它的质因子去 check 每个 GCD 即可。

考虑反复横跳能跳到相邻点以代价 2，并且能以代价 1 到达墙壁。直接按这个跑最短路就行了。分析一下容易发现肯定是不会走自交的路径的，因为这样不优，所以可得出这样走出来的路径一定合法。

很牛的 thinking。

考虑求出“前 $t$ 时刻，经过 $(x, y)$ 的露米娅个数”。

这个其实不难求：如果有 $k$ 个露米娅来到了这个点，因为每次离开都会使得送往方向变化，那么恰好有 $⌈ \frac{k}{2} ⌉$ 被送到右边， $⌊ \frac{k}{2} ⌋$ 被送到下边。然后我们跑一个 $O (n^{2})$ 的 dp 就可以求出以上问题了。

dp 初值 $d p_{0, 0} = t - x - y + 1$ ，因为 $t - x - y + 1$ 时刻之后的都无法到达 $(x, y)$ 。

然后回到原问题，我们差分一下，相当于对前 $t$ 时刻和前 $t - 1$ 时刻分别做一次上述问题，判断是否有新增即可。

一个点 $x$ 在树上按照某种规则走路，求最后会走到哪。

这个可以先考虑如何判断 $x$ 是否会经过 $y$ ，然后进行树链剖分。