P6476 [NOI Online #2 提高组] 涂色游戏

1s 256M

你有 $10^{20}$ 个格子，它们从 $0$ 开始编号，初始时所有格子都还未染色，现在你按如下规则对它们染色： 1. 编号是 $p_1$ 倍数的格子（包括 $0$ 号格子，下同）染成红色。 2. 编号是 $p_2$ 倍数的格子染成蓝色。 3. 编号既是 $p_1$ 倍数又是 $p_2$ 倍数的格子，你可以选择染成红色或者蓝色。 其中 $p_1$ 和 $p_2$ 是给定的整数，若格子编号是 $p_1$ 或 $p_2$ 的倍数则它必须要被染色。在忽略掉所有未染色格子后，你不希望存在 $k$ 个连续的格子颜色相同，因为你认为这种染色方案是无聊的。现在给定 $p_1$, $p_2$, $k$，你想知道是否有一种染色方案不是无聊的。

无

无

| 测试点编号 | $p_1$, $p_2 \leq$ | $k \leq$ | $T \leq$ | | :-- | :-- | :-- | :-- | | 1 $\sim$ 3 | $15$ | $15$ | $3375$ | | 4 $\sim$ 6 | $10^3$ | $10^3$ | $10^4$ | | 7 $\sim$ 8 | $10^3$ | $10^3$ | $10$ | | 9 $\sim$ 10 | $10^5$ | $10^3$ | $10^3$ | | 11 $\sim$ 12 | $10^5$ | $5 \times 10^5$ | $10$ | | 13 $\sim$ 14 | $10^5$ | $5 \times 10^5$ | $10^5$ | | 15 | $10^9$ | $10^9$ | $10$ | | 16 $\sim$ 20 | $10^9$ | $10^9$ | $10^6$ | 对于所有测试点：$1 \leq T\leq 10^6$，$1\leq p_1,p_2$，$k\le 10^9$。