← 返回题目列表

AtCoder · arc118_d

D. 哈密顿循环

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

分数: 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,打印序列中的元素 A 满足下一行的要求,中间有空格。

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