Codeforces Round #174 Div2 - くじらにっき++

A. Cows and Primitive Roots

http://www.codeforces.com/problemset/problem/284/A

素数pについて x - 1, x² - 1, ..., x^p-2 - 1 (mod p) != 0 かつ x^p-1 (mod p) == 0 が成り立つx (1 <= x < p) を、pのPrimitive Rootといいます。日本語では「原始根」といいます。

素数pを与えるので、原始根の個数を表示して下さい。

原始根についての解説はこちらが詳しいです。が、高度すぎて私にはさっぱり理解出来ません^^;

既約剰余類群と原始根 - epii's physics notes

実は、xがpの原始根であるときは gcd(p-1, x) が成り立つという性質があるということなので、オイラーのΦ関数を使えば一発で解けるようなのですが、そんなことはGoogle先生に聞かないと分からない（というのが普通だと思うのですが…）ので、問題文に書いてあることを愚直に実装しましょう。A問題ですし。

しかしながら、pの値が取る範囲は 2 <= p < 2000 となっているので、 x^p-1 なんて計算できません。ここで mod p に着目する必要があります。

蟻本にも書いてありますが（第2版なら114ページ）、 a%m == c%m かつ b%m == d%m のときは以下の3つの等式が成り立ちます

(a + b)%m == (c + d)%m
(a - b)%m == (c - d)%m
(a * b)%m == (c * d)%m

ここから、大きな累乗の余りを求めるのに便利な方法が導き出せます。

(k*k)%m を求める場合について考えてみましょう。

上の式より ( (k%m)*(k%m) )%m ですね。

次に (k*k*k)%m について考えてみましょう。

こちらは (k*k)%m の結果を流用することにすると ( ((k*k)%m)*(k%m) )%m となりますね。

x^k が桁あふれを起こす場合でも x^k%mは m < sqrt(INT_MAX) ならば桁あふれを起こさずに計算できることが分かるかと思います。

余りを取りながら累乗を計算するときには「繰り返し二乗法」によって高速化することもできます（詳細は蟻本を参照して下さい）。ICPC用のライブラリに入れるのを忘れていたので、今日にでもライブラリ化しようと思います。ただし、今回は、たかだか2000回のループをするだけで良いので繰り返し二乗法は必要ないような気もします。

僕はクズなので、Pythonの標準ライブラリに含まれているpow()関数を使いました。pythonのpow()関数には第3引数があって、x**y%zを高速に計算してくれます。

しかしながら、そこまで知っていつつもxrange()の引数を勘違いしていて、全く点数を稼げませんでした。xrange(a,b) は [a, a+b) ではなくて [a, b) です。みなさん勘違いしないようにしましょう！！！