Power Pair
まず P の原始根をひとつ取り r とおく
x = r^a (mod P) とおく (原始根の性質から、このような a が x に対してただひとつ存在する)
同様に y = r^b とおく
このとき元の条件は
$ x^n \equiv y \pmod{P} \Leftrightarrow r^{an} \equiv r^b \pmod{P}
と変形できる
フェルマーの小定理から ($ an = \triangle \times (P - 1) + \diamondsuit の形で表して考えると) 上の条件は
$ an \equiv b \pmod{P - 1}
となる
a を fix して条件を満たす b を数えよう
a, 2a, 3a, ... (mod P - 1) の周期性を考える
→ b は P - 1 個
例: a = 3, P - 1 = 5
code:a=3, P-1=5
3, 6, 9, 12, 15, 18, 21, 24, ...
3, 1, 4, 2, 0, 3, 1, 4, ... (mod P-1)
一般に gcd(a, P - 1) = g のときは (P - 1) / g 周期になる (?)
結局$ \sum_{a = 1}^{P - 1} (P - 1) / \gcd(a, P - 1)が答えになるとわかった
d = gcd(a, P - 1) ごとに数えよう
f(d) を、a = 1, 2, ..., P - 1 のうち d = gcd(a, P - 1) となる a の個数、とおく
上の式は$ \sum_{d|(P-1)} f(d) (P - 1) / dと変形できる
f(d) は「a = 1, 2, ..., P - 1 のうち gcd(a, P - 1) が d の倍数となる a の個数」= (P - 1) / d
から
f(2d)
f(3d)
...
を引いたものだから d の降順に求められる