AtCoder Beginner Contest 340 题解

PikachuQAQ · 2024-02-11 14:46:18 · 题解

ABC340 题解

去博客园里看这篇文章！

模拟即可。

用 vector 模拟即可。

丢到 OEIS 里得到规律即可。

我们可以把这个问题转化为最短路问题。

对于每个点 i 建两条到 i + 1 和到 x_i 的边，边权分别为 a_i 和 b_i，求点 1 到点 n 的最短路即可。

可以把操作转为给每个 i 加上 \lfloor\dfrac{n}{b_i}\rfloor，将剩下的 n 取出来给相应区间加 1。当要加 1 的 i 超过 n，那么将多出来的区间从 1 开始补到后面即可。

注意到已知其中两个点坐标分别为 (a,b) 和 (0,0)，面积为 S，则有 \dfrac{|ay-bx|}{2}=1，据题得 ay-bx=±2。这种形式的方程，可以用 exgcd 解决。当 a 和 b 的最大公因数大于 2，那么无解。

我们通过 exgcd 得到了一对解，为 ay_0-bx_0=±\gcd(a,b)，将 (x_0,y_0) 分别除以 -\dfrac{g}{2} 和 \dfrac{g}{2} 即可得到正确解 (x,y)。

不会虚树。