更好的阅读体验

T1

题意:给出$a,b,k$,要求$a$的倍数格子填颜色1,$b$的倍数格子填颜色2,是$ab$倍数的格子颜色任选.求是否存在一种填法,满足忽略掉无色格子后不存在$k$个连续的同色格子.

$1\le a,b,k\le 10^9$

解:若$k=1$,必然不存在.

若$a<b,a,b$互素,则$ax\ mod\ b$必然取遍$[0,b-1]$.设$ax\ mod\ b=1$.则$[1,b-1]$这一段中恰有$\lfloor \frac{(b-2)}{a}\rfloor +1$ 个格子是颜色1.也就是无论是$ab$倍数的格子怎么填,都至少有$\lfloor \frac{(b-2)}{a}\rfloor +1$个连续的无色格子.且将$ab$倍数的格子都填颜色2时,可以得到至多有$\lfloor \frac{(b-2)}{a}\rfloor +1$个连续的无色格子.所以当且仅当$\lfloor \frac{(b-2)}{a}\rfloor +1 < k$时有解.

对于一般情况,令$a/gcd(a,b),b/gcd(a,b)$即可规约到$a,b$互素之情况.

每组数据时间复杂度$\mathcal O(\log min(a,b))$

code