P6476 [NOI Online #2 Senior] Coloring Game

1s 256M

You have $10^{20}$ cells, numbered starting from $0$. Initially, all cells are uncolored. Now you color them according to the following rules: 1. Cells whose indices are multiples of $p_1$ (including cell $0$, same below) are colored red. 2. Cells whose indices are multiples of $p_2$ are colored blue. 3. For cells whose indices are multiples of both $p_1$ and $p_2$, you may choose to color them red or blue. Here $p_1$ and $p_2$ are given integers. If a cell index is a multiple of $p_1$ or $p_2$, then it must be colored. After ignoring all uncolored cells, you do not want there to be $k$ consecutive cells with the same color, because you think such a coloring scheme is boring. Given $p_1$, $p_2$, and $k$, you want to know whether there exists a coloring scheme that is not boring.

This problem contains multiple test cases. The first line contains an integer $T$ indicating the number of test cases. Each test case consists of one line with three positive integers $p_1$, $p_2$, $k$, with meanings as described above.

For each test case, output one line with a string. If there exists a coloring scheme that is not boring, output `YES`, otherwise output `NO`. Any output format that matches one of the formats in the samples or the statement is accepted, i.e. it is case-insensitive. For example, if the standard answer is `YES`, then `YES/Yes/yes` are all considered correct.

| Test Point ID | $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$ | Constraints for all test points: $1 \leq T \leq 10^6$, $1 \leq p_1, p_2, k \leq 10^9$. Translated by ChatGPT 5