题解 P5444 【[APIO2019]奇怪装置】

SamariumPhosphide · 2020-08-14 08:24:26 · 题解

这道题还是比较水的。

首先显然我们不能考虑怎么样会不同，而是应该考虑什么情况会相同。

不妨假设在 t 和 t' 的时间相同，不妨 t' > t。

那么 t' \equiv t (\mod B)。设 t' = t + Bx。

那么 t + \lfloor \frac{t}{B}\rfloor \equiv t + Bx + \lfloor \frac{t}{B} \rfloor + x (\mod A)。

所以 bx + x \equiv 0 (\mod A)。

所以 A | (b+1)x \Rightarrow \frac{A}{\gcd(A, B+1)} | x。

因此相等的循环节是 Bx = \frac{AB}{\gcd(A, B+1)}。

那么我们考虑在这个循环节中有多少可以取到，也就是给出若干条线段在 [0,Bx] 之间的线段，求总覆盖长度。

贪心即可。

Code