← 返回题目列表

AtCoder · arc166_f

F. 切线加法公式

中文机器翻译题面 查看原题

分数: 1100 点

问题陈述

给你一个素数 p 和非负整数 a 和 b.

判断是否存在无限非负整数序列 t = \bigl(t(0), t(1), t(2), \ldots) 满足以下所有条件。

  • 0\leq t(x) < p 对于每个非负整数 x.
  • t(x+y)\bigl(1-t(x)t(y)\bigr)\equiv t(x)+t(y)\pmod{p} 对于所有非负整数 x 和 y.
  • t(a)=b.

你有 T 测试用例解决。

约束

  • 1\leq T\leq 2\times 10^5
  • p 是素数,使得 1\leq p\leq 10^9.
  • 0\leq a\leq 10^{9}
  • 0\leq b < p

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

p a b

输出

打印 T 行。的 i- 第行应包含 Yes 如果存在满足所有条件的非负整数序列,并且 No 否则。


示例输入 1

4
11 1 0
11 1 1
11 1 3
11 1 5

示例输出 1

Yes
No
No
Yes
  • 对于 p=11, a=1, b=0,一个常数序列 t = (0,0,0,0,\ldots) 满足条件。
  • 对于 p=11, a=1, b=5,一个序列 t = (0,5,6,0,5,6,\ldots) 期间 3 满足条件。

示例输入 2

5
5 0 0
5 1 1
5 2 2
5 3 3
5 4 4

示例输出 2

Yes
No
Yes
Yes
No

示例输入 3

7
2 3 1
2 5 0
5 0 1
5 0 2
7 1 4
11 12345 5
13 12345 5

示例输出 3

Yes
Yes
No
Yes
No
No
Yes