Search on the blog

2013年3月30日土曜日

Codeforces Round #174 Cows and Primitive Roots

Div2 Aだけど面白い問題。

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

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

別解
ここにあるとおり。

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

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

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

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

0 件のコメント:

コメントを投稿