分数: 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