Tangent Addition Formula

AtCoder

IDarc166_f

Time10000ms

Memory256MB

Difficulty—

You are given a prime number $p$ and non-negative integers $a$ and $b$. Determine if there is an infinite sequence of non-negative integers $t = \bigl(t(0), t(1), t(2), \ldots)$ that satisfies all of the following conditions. * $0\leq t(x) < p$ for every non-negative integer $x$. * $t(x+y)\bigl(1-t(x)t(y)\bigr)\equiv t(x)+t(y)\pmod{p}$ for all non-negative integers $x$ and $y$. * $t(a)=b$. You have $T$ test cases to solve. ## Constraints * $1\leq T\leq 2\times 10^5$ * $p$ is a prime number such that $1\leq p\leq 10^9$. * $0\leq a\leq 10^{9}$ * $0\leq b < p$ ## Input The input is given from Standard Input in the following format: $T$ $\text{case}_1$ $\vdots$ $\text{case}_T$ Each test case is given in the following format: $p$ $a$ $b$ [samples]

Samples

Input #1

Output #1

Yes
No
No
Yes

*   For $p=11, a=1, b=0$, a constant sequence $t = (0,0,0,0,\ldots)$ satisfies the conditions.
*   For $p=11, a=1, b=5$, a sequence $t = (0,5,6,0,5,6,\ldots)$ of period $3$ satisfies the conditions.

Input #2

Output #2

Yes
No
Yes
Yes
No

Input #3

Output #3

Yes
Yes
No
Yes
No
No
Yes

API Response (JSON)

{
  "problem": {
    "name": "Tangent Addition Formula",
    "description": {
      "content": "You are given a prime number $p$ and non-negative integers $a$ and $b$. Determine if there is an infinite sequence of non-negative integers $t = \\bigl(t(0), t(1), t(2), \\ldots)$ that satisfies all of ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc166_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a prime number $p$ and non-negative integers $a$ and $b$.\nDetermine if there is an infinite sequence of non-negative integers $t = \\bigl(t(0), t(1), t(2), \\ldots)$ that satisfies all of ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments