/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
素数 p および，非負整数 a, b が与えられます．
長さ無限の非負整数列 t = \bigl(t(0), t(1), t(2), \ldots) であって，以下の条件を全て満たすものが存在するか否かを判定してください．
- 任意の非負整数 x に対して 0\leq t(x) < p．
- 任意の非負整数 x, y に対して t(x+y)\bigl(1-t(x)t(y)\bigr)\equiv t(x)+t(y)\pmod{p}．
- 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 行目には i 番目のテストケースについて，条件を満たす非負整数列 t が存在するならば 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 の場合：周期 3 の数列 t = (0,5,6,0,5,6,\ldots) が条件を満たします．
入力例 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
Score : 1100 points
Problem Statement
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
Output
Print T lines. The i-th line should contain Yes if there is a sequence of non-negative integers that satisfies all of the conditions, and No otherwise.
Sample Input 1
4 11 1 0 11 1 1 11 1 3 11 1 5
Sample 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.
Sample Input 2
5 5 0 0 5 1 1 5 2 2 5 3 3 5 4 4
Sample Output 2
Yes No Yes Yes No
Sample Input 3
7 2 3 1 2 5 0 5 0 1 5 0 2 7 1 4 11 12345 5 13 12345 5
Sample Output 3
Yes Yes No Yes No No Yes