Yukicoder 984 Inversion - tarattataのブログ

問題の概要

素数 $P$ と正整数 $N$ が与えられる。
数列 $a_{i}=(i ⋅ N) \bmod P$ $(i=1,2,..,N)$
について、その転倒数の偶奇を求めよ。（偶なら0、奇なら1を出力）
※ $\bmod P$ は、 $P$ で割った余り

制約

$2 \le P \le 2^{31}-1$
$1 \le N \le P-1$

解法

例えば、 $P=3, N=13$ の場合、数列は以下のようになります。
$3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, 10$
この数列の転倒数の偶奇ということは、この数列（順列）を $i→a_{i}$ という置換とみなしたときに偶置換か奇置換か、を求める問題です。

偶置換か奇置換かの判定は、例えば、サイクルを観察するとわかります。
一般に、ある置換をサイクル(巡回置換)に分解したとき、その長さを $L_{1}, L_{2},..,L_{m}$ とすると、 $\sum (L_{i}-1)$ の偶奇が、偶置換か奇置換かの答になります（巡回置換を互換の積に表せばよい）。例えば上の例では、 $(1,3,9), (2, 6, 5), (4, 12, 10), (7, 8, 11)$ という 4つのサイクル（巡回置換）に分解されるので、偶置換とわかります。

今回の問題では、1を含むサイクルは集合としては $A=\lbrace N^{i}\rbrace$ で、その要素数を $M$ とおくと、他のサイクルも（例えば要素 $a$ を含むサイクルは $a⋅A$ という形になって）要素数が $M$ になるので、 $M$ は $(P-1)$ の約数で、 $(M-1)⋅\frac{P-1}{M}$ の偶奇が答になります。

あとは $M$ を求められればよいのですが、 $N^{i} \bmod P$ が 1 に等しくなるような最小の正整数 $i$ を求めるという話なので、Baby-step Giant-step algorithm などで解くことができます。

※ 実は、 $P$ が奇素数の場合には、 $(M-1)⋅\frac{P-1}{M}$ が偶数であることは $\frac{P-1}{M}$ が偶数であることと同値になり、 $N$ が $P$ の平方剰余であることと同値になるので、それを使って判定することもできます。（ $N^{\frac{p-1}{2}} \bmod P$ が1か否かで判定）

※ 数学的な書き方では、 $P$ が奇素数の場合、 $(Z/pZ)^{×}$ に対して要素 $N$ を生成元とする巡回部分群を考えて、それによる商群の位数の偶奇を答えるという問題でした。

解答例

https://yukicoder.me/submissions/428793