Codeforces Round #174 Cows and Primitive Roots

Div2 Aだけど面白い問題。

問題概要

素数pが与えられる。法pにおける原始根の数を数えよ。(p < 2000)

解法

各整数1 <= x < pについて、原始根になるかどうか愚直に調べればいい。計算量はO(p²)。
これで十分間に合うがもっと効率的な解法がある。

別解

ここにあるとおり。

まず、pは素数なので必ず少なくとも１つの原始根が存在する。それをgとおく。
gは原始根なので、{g, g², g³,...,g^p-1}と{1,2,...p-1}はmod pにおいて同じ集合を表す。
よって、{1,2,...,p-1}の中で原始根になる数の個数と{g, g², g³,...,g^p-1}の中で原始根になる数の個数は同じ。

{g, g², g³,...,g^p-1}の中で原始根になるのはどれか考える。
gcd(i, p-1) > 1であるとき、g^{i * (p-1)/gcd(i, p-1)} = g^{(p-1) * i/gcd(i, p-1)} = 1^{i/gcd(i, p-1)} = 1
なので、gⁱは原始根ではない。

gcd(i, p-1) = 1のとき、(p-1) | (i * x) となるような最小のxは(p-1)なので、gⁱは(p-1)乗したときにはじめて1になる。よってこれは原始根。

以上のことから、φ(p-1)が答えとなる。ここでφはオイラーのtotient function。
計算量はsqrt(p)。