ARC127 F

加藤惠 · 2021-10-01 21:16:13 · 个人记录

先把 V 对 B 取模，显然我们只要考虑 [0,B) 中哪些数可以搞出来，因为一个不在这个区间内的数 x 可以被搞出来当且仅当 x \bmod B 可以被搞出来。

显然如果 A+B\le M+1，答案是 M+1。

稍加思考不难发现之后会进行的操作只有两种

• 加一次 A，然后一直减 B 直到不能减。

• 一直加 B 直到不能加，然后减一次 A。

当然能够执行一种操作需要 V 满足一些条件，大概就是 V 的值需要在一个区间内。

前者会使 V\to (V+(A\bmod B))\bmod B，后者会使 V\to (V+B-(A\bmod B))\bmod B。

于是我们肯定是一直执行操作 1 到不能执行，再一直执行操作 2，期间搞到的数就是所有我们能搞出来的数。

可以二分，然后问题转化为判断 \forall i\in[0,n],(ai+b)\bmod c\in [l,r]，这是个经典问题，随便类欧判下就行。

复杂度是两个 \log 的，常数有一点点大。

看了眼官方题解，似乎是一个 \log 的，有空再补。