[ICPC 2024 Xi'an I] Chained Lights

Luogu

IDLGP10565

Time1000ms

Memory1024MB

DifficultyP2

2024O2优化ICPC西安

You have $n$ lights in a row. Initially, they are all off. You are going to press these $n$ lights one by one. When you press light $i$, light $i$ will switch its state, which means it will turn on if it's off and turn off if it's on, and then for every $j$ satisfied $i|j,i< j\le n$, press light $j$ once. For example, if $n=4$, when you press light $1$, light $1$ will turn on, and then you will press light $2,3,4$. Since you pressed light $2$, light $2$ will turn on and you will press light $4$, which will cause light 4 to turn on. After all the operations, lights $1,2,3$ will be turned on and light $4$ is still off. You will press these $n$ lights and do the operations as mentioned above one by one. After all the operations, you want to know whether light $k$ is on or off. You can also use the following code to understand the meaning of the problem: ```cpp void press(int x) { light[x]^=1; for (int y=x+x;y<=n;y+=x) press(y); } for (int i=1;i<=n;i++) press(i); ``` ## Input There are multiple testcases. The first line contains an integer $T(1\le T\le10^5)$, which represents the number of testcases. Each of the testcases contains two integers $n,k(1\le k\le n\le10^6)$ in a single line. ## Output For each testcase, if light $k$ is turned on in the end, output $\text{YES}$, otherwise output $\text{NO}$. [samples]

Samples

Input #1

2
1 1
3 2

Output #1

YES
NO

API Response (JSON)

{
  "problem": {
    "name": "[ICPC 2024 Xi'an I] Chained Lights",
    "description": {
      "content": " You have $n$ lights in a row. Initially, they are all off.                You are going to press these $n$ lights one by one. When you press light $i$, light $i$ will switch its state, which means it",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10565"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have $n$ lights in a row. Initially, they are all off.\n    \n    \n    \nYou are going to press these $n$ lights one by one. When you press light $i$, light $i$ will switch its state, which means it ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments