/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
素数 P および正の整数 a, b が与えられます。 P 項からなる整数列 A = (A_1, A_2, \ldots, A_P) であって、次の条件をすべて満たすものが存在するかを判定してください。 存在する場合には、そのようなものをひとつ出力してください。
- 1\leq A_i\leq P - 1
- A_1 = A_P = 1
- (A_1, A_2, \ldots, A_{P-1}) は、(1, 2, \ldots, P-1) を並べ替えたものである
- 任意の 2\leq i\leq P に対して、次のうち少なくともひとつが成り立つ：
- A_{i} \equiv aA_{i-1}\pmod{P}
- A_{i-1} \equiv aA_{i}\pmod{P}
- A_{i} \equiv bA_{i-1}\pmod{P}
- A_{i-1} \equiv bA_{i}\pmod{P}
制約
- 2\leq P\leq 10^5
- P は素数
- 1\leq a, b \leq P - 1
入力
入力は以下の形式で標準入力から与えられます。
P a b
出力
問題の条件を満たす整数列 A が存在するならば Yes を、そうでなければ No を出力してください。
Yes の場合には、2 行目にそのような整数列 A の各要素を、空白で区切って 1 行で出力してください。
A_1 A_2 \ldots A_P
条件を満たす整数列が複数存在する場合は、どれを出力しても正解となります。
入力例 1
13 4 5
出力例 1
Yes 1 5 11 3 12 9 7 4 6 8 2 10 1
P = 13 を法として、
- A_2\equiv 5A_1
- A_2\equiv 4A_3
- \vdots
- A_{13}\equiv 4A_{12}
が成り立ち、この整数列は条件を満たすことが確認できます。
入力例 2
13 1 2
出力例 2
Yes 1 2 4 8 3 6 12 11 9 5 10 7 1
入力例 3
13 9 3
出力例 3
No
入力例 4
13 1 1
出力例 4
No
Score : 700 points
Problem Statement
Given are a prime number P and positive integers a and b. Determine whether there is a sequence of P integers, A = (A_1, A_2, \ldots, A_P), satisfying all of the conditions below, and print one such sequence if it exists.
- 1\leq A_i\leq P - 1.
- A_1 = A_P = 1.
- (A_1, A_2, \ldots, A_{P-1}) is a permutation of (1, 2, \ldots, P-1).
- For every 2\leq i\leq P, at least one of the following holds.
- A_{i} \equiv aA_{i-1}\pmod{P}
- A_{i-1} \equiv aA_{i}\pmod{P}
- A_{i} \equiv bA_{i-1}\pmod{P}
- A_{i-1} \equiv bA_{i}\pmod{P}
Constraints
- 2\leq P\leq 10^5
- P is a prime.
- 1\leq a, b \leq P - 1
Input
Input is given from Standard Input in the following format:
P a b
Output
If there is an integer sequence A satisfying the conditions, print Yes; otherwise, print No.
In the case of Yes, print the elements in your sequence A satisfying the requirement in the next line, with spaces in between.
A_1 A_2 \ldots A_P
If multiple sequences satisfy the requirement, any of them will be accepted.
Sample Input 1
13 4 5
Sample Output 1
Yes 1 5 11 3 12 9 7 4 6 8 2 10 1
This sequence satisfies the conditions, since we have the following modulo P = 13:
- A_2\equiv 5A_1
- A_2\equiv 4A_3
- \vdots
- A_{13}\equiv 4A_{12}
Sample Input 2
13 1 2
Sample Output 2
Yes 1 2 4 8 3 6 12 11 9 5 10 7 1
Sample Input 3
13 9 3
Sample Output 3
No
Sample Input 4
13 1 1
Sample Output 4
No