AT_arc118_d.[ARC118D] Hamiltonian Cycle

给定素数 $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}$

输入从标准输入读入，格式如下：

$P$ $a$ $b$

如果存在满足条件的整数序列 $A$，输出 Yes，否则输出 No。如果输出 Yes，第二行输出该整数序列 $A$ 的各个元素，空格分隔。

$A_1\ A_2\ \ldots\ A_P$

如果存在多个满足条件的序列，输出任意一个均可。

数据范围

• $2 \leq P \leq 10^5$
• $P$ 是素数
• $1 \leq a, b \leq P-1$

样例解释 1

以 $P=13$ 为例，满足以下条件：

• $A_2 \equiv 5A_1$
• $A_2 \equiv 4A_3$
• $\vdots$
• $A_{13} \equiv 4A_{12}$

可以确认该整数序列满足所有条件。

由 ChatGPT 4.1 翻译