B - Symmetric Painting Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600

問題文

円周上を N 等分する位置に、点 0,1, \ldots , N-1 がこの順に並んでおり、Alice が点 0 に、Bob が点 K にいます。また、初め全ての点は白色に塗られています。両者は、Alice から始めて交互に次のような操作を行います。

  • その時点で白色である点を 1 つ選び、黒色に塗る。ただし、操作後に、操作者と円の中心を結ぶ直線に対して、各点の色が線対称でなければいけない。

操作者が上記の条件を満たす操作ができなければ、そこで一連の操作を打ち切ります。

両者とも、最終的に最も多くの点を黒く塗ることができるように協力して最善の選択をします。一連の操作が全て終了したときに全ての点を黒く塗ることができているかどうかを求めてください。

T 個のテストケースが与えられるので、それぞれについて答えてください。

制約

  • 1\leq T\leq 10^5
  • 2\leq N\leq 2\times 10^5
  • 1\leq K\leq N-1
  • 入力される値はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots 
\mathrm{case}_T

各テストケース \mathrm{case}_i (1\leq i \leq T) は以下の形式である。

N K

出力

T 行出力せよ。i 行目には、i 番目のテストケースについて、全ての点を黒く塗ることができるなら Yes 、できないなら No と出力せよ。


入力例 1

4
6 2
6 3
6 1
200000 100000

出力例 1

Yes
No
Yes
No

N=6, K=2 の場合、例えば以下のような順で操作を行うことで全ての点を黒く塗ることができます。

  1. Alice が点 3 を黒く塗る。
  2. Bob が点 1 を黒く塗る。
  3. Alice が点 5 を黒く塗る。
  4. Bob が点 2 を黒く塗る。
  5. Alice が点 4 を黒く塗る。
  6. Bob が点 0 を黒く塗る。

N=6, K=3 の場合、例えば以下のような進行が考えられます。実は、どのようにしても全ての点を黒く塗ることはできません。

  1. Alice が点 3 を黒く塗る。
  2. Bob が点 0 を黒く塗る。
  3. Alice はどの点を黒く塗っても自身から見て線対称にできないため、操作を行えない。

Score : 600 points

Problem Statement

On a circle, there are N equally spaced points numbered 0,1,\ldots,N-1 in this order, with Alice at point 0 and Bob at point K. Initially, all points are colored white. Starting with Alice, they alternately perform the following operation:

  • Choose one of the currently white points and color it black. Here, after the operation, the coloring of the points must be symmetric with respect to the straight line connecting the operator and the center of the circle.

If the operator cannot perform an operation satisfying the above condition, the sequence of operations ends there.

Both players cooperate and make the best choices to maximize the total number of points colored black in the end. Determine whether all points are colored black at the end of the sequence of operations.

You are given T test cases to solve.

Constraints

  • 1 \leq T \leq 10^5
  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq N-1
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots 
\mathrm{case}_T

Each test case \mathrm{case}_i (1 \leq i \leq T) is in the following format:

N K

Output

Print T lines. The i-th line should contain Yes if all points can be colored black for the i-th test case, and No otherwise.


Sample Input 1

4
6 2
6 3
6 1
200000 100000

Sample Output 1

Yes
No
Yes
No

For N=6 and K=2, all points can be colored black by, for example, performing operations in the following order:

  1. Alice colors point 3 black.
  2. Bob colors point 1 black.
  3. Alice colors point 5 black.
  4. Bob colors point 2 black.
  5. Alice colors point 4 black.
  6. Bob colors point 0 black.

For N=6 and K=3, below is one possible progression. Actually, no matter what they do, they cannot color all points black.

  1. Alice colors point 3 black.
  2. Bob colors point 0 black.
  3. Alice cannot color any point black so that the coloring will be symmetric with respect to her line, so she cannot perform the operation.