AtCoder Regular Contest 118 D

https://atcoder.jp/contests/arc118/tasks/arc118_d

面白かったので解説してみます。

P = 13, a = 4, b = 5で考えてみます。
まず、グラフを描いてみましょう。

a倍していくと、
1 -> 4 -> 3 -> 12 -> 9 -> 10 -> 1
と周期6になります。
もう1つサークルがあります。
2 -> 8 -> 6 -> 11 -> 5 -> 7 -> 2

b倍していくと周期4が3つあります。
1 -> 5 -> 12 -> 8 -> 1
2 -> 10 -> 11 -> 3 -> 2
4 -> 7 -> 9 -> 6 -> 4

この2つの周期のサークルが絡み合っているので難しそうですよね。

さて、素数pに対して1 ～ p-1はaを適当に選ぶと周期p-1のサークルになります。p = 13に対してa = 6とすると、
1 -> 6 -> 10 -> 8 -> 9 -> 2 -> 12 -> 7 -> 3 -> 5 -> 4 -> 11 -> 1
周期12になります。
g = 6と置くと、 4 \equiv g^{10}なので、a倍していくサークルは、
1 \equiv g^0 \rightarrow g^{10} \rightarrow g^{20} \rightarrow g^{30} \rightarrow g^{40} \rightarrow g^{50} \rightarrow g^{60} \equiv 1
2 \equiv g^5 \rightarrow g^{15} \rightarrow g^{25} \rightarrow g^{35} \rightarrow g^{45} \rightarrow g^{55} \rightarrow g^{65} \equiv 2

5 \equiv g^9なので、b倍していくサークルは、
1 \equiv g^0 \rightarrow g^9 \rightarrow g^{18} \rightarrow g^{27} \rightarrow g^{36} \equiv 1
2 \equiv g^5 \rightarrow g^{14} \rightarrow g^{23} \rightarrow g^{32} \rightarrow g^{41} \equiv 2
4 \equiv g^{10} \rightarrow g^{19} \rightarrow g^{28} \rightarrow g^{37} \rightarrow g^{46} \equiv 4

指数だけ見ましょう。そうすると、掛け算は足し算になって、12を法とする剰余を考えます。そして、指数を並べると、a倍を横、b倍を縦に並べて、

36 46 56 66 76 86 96
27 37 47 57 67 77 87
18 28 38 48 58 68 78
 9 19 29 39 49 59 69
 0 10 20 30 40 50 60

一番左と右、一番下と上は同じ数を表しています。つまり、上下左右に無限に伸びています。トーラスですね。
グラフの辺は、それぞれ数とその上下左右の数を結びます。
パスは、下の2行だけ考えて、

 9 → 19    29 → 39    49 → 59
 ↑    ↓    ↑     ↓    ↑     ↓
 0    10 → 20    30 → 40    50 → 60

とすればよいです。この方法は、横の周期が偶数だと成り立ちます。
ただし、b = 10だとパスはありません。なぜなら、 10 \equiv g^2なので、1にどうaとbを掛けても指数は偶数になってしまい、奇数は表せないからです。
a \equiv g^{e_a}とすると、周期は p_a = (P-1)/\gcd{(P-1, e_a)}となります。逆に周期が分かっていたら、 \gcd{(P-1, e_a)} = (P-1)/p_aとなります。bの方の周期を p_bとすると、

\gcd{(P-1, \gcd{(e_a, e_b)})} = \gcd{((P-1)/p_a, (P-1)/p_b)}

となります。これが1でないならパスは無しです。
周期はaを次々と掛けていけば得られると思いますが、周期はP-1の約数なので、約数の小さい順にべき乗の計算をすればよいでしょう。

最後に、横の周期を必ず偶数にできるかです。 p_a, p_bのどちらかが偶数になればいいので、どちらも奇数があり得るか考えます。
P-1はP=2以外では偶数です（P=2のときは、1 → 1というパスでOKです）。 p_a, p_bが共に奇数なら、 \gcd{((P-1)/p_a, (P-1)/p_b)}は偶数になります。

以下は、PyPy2のコードです。

# coding: utf-8
# Hamiltonian Cycle

from itertools import *
from fractions import gcd
import sys


#################### library ####################

def factorize_naive(n):
	def f(n, p0):
		if n <= 1:
			return ()
		
		for p in takewhile(lambda p: p * p <= n, count(p0)):
			if n % p == 0:
				return (p,) + f(n / p, p)
		else:
			return (n,)
	
	return list((k, len(list(v))) for k, v in groupby(f(n, 2)))

def divisors_f(fs):
	if len(fs) == 1:
		p, e = fs[0]
		for e1 in range(e+1):
			yield p**e1
	else:
		mid = len(fs) / 2
		ds1 = list(divisors_f(fs[:mid]))
		ds2 = list(divisors_f(fs[mid:]))
		for d1 in ds1:
			for d2 in ds2:
				yield d1 * d2

def period(e, p):
	fs = factorize_naive(p - 1)
	ds = sorted(divisors_f(fs))
	for d in ds:
		if pow(e, d, p) == 1:
			return d


#################### process ####################

def read_input():
	P, a, b = tuple(map(int, raw_input().split()))
	return (P, a, b)

def is_valid(path, P, a, b):
	if len(path) != P:
		return False
	
	s = set(path[:-1])
	if len(s) != P - 1:
		return False
	
	for v1, v2 in zip(path, path[1:]):
		if not (a * v1 % P == v2 or a * v2 % P == v1 or
				b * v1 % P == v2 or b * v2 % P == v1):
			return False
	else:
		return True

def Hamiltonian_Cycle(P, a, b):
	def generate_path(p1, e1, p2, e2):
		for i in range(p1):
			if i % 2 == 0:
				for j in range(p2):
					yield pow(e1, i, P) * pow(e2, j, P) % P
			else:
				for j in range(p2 - 1, -1, -1):
					yield pow(e1, i, P) * pow(e2, j, P) % P
		yield 1
	
	if P == 2:
		return [1, 1]
	
	pa = period(a, P)
	pb = period(b, P)
	if gcd((P - 1) / pa, (P - 1) / pb) != 1:
		return []
	
	if pa % 2 == 0:
		return list(generate_path(pa, a, (P - 1) / pa, b))
	else:
		return list(generate_path(pb, b, (P - 1) / pb, a))


#################### main ####################

P, a, b = read_input()
cycle = Hamiltonian_Cycle(P, a, b)
#print(is_valid(cycle, P, a, b))
if cycle:
	print('Yes')
	print(' '.join(map(str, cycle)))
else:
	print('No')