WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #174 Div2 A "Cows and Primitive Roots"

問題

整数Pが与えられる。
1 <= x < Pの範囲内で、
x^1 - 1 mod p != 0
x^2 - 1 mod p != 0
x^3 - 1 mod p != 0
.
.
.
x^(p-2) - 1 mod p != 0
で、
x^(p-1) - 1 mod p == 0

のようなxは何個あるか返せ。

制約

2 <= P <= 2000

考えた事

Pが2000だと1999^2000 - 1とかやんなきゃいけないな
ま、後々modをうまく使えばなんとかなるっしょ。

よし、実装完了。Sample通る
じゃあPがでかい時の対策しますか。

あれ・・・
乗数に途中でmod入れると計算狂っちゃうよね・・・
どーしよどーしよどーしよどーしよどー(パニック)
わああもう30分経つ!

  粘る
→ Bに逃げる

よしBは余裕だった。もっかいチャレンジ。
なんか法則を探すんだ!

ん?なんか途中でmodしても大丈夫だぞ?

3  mod 5 == 3 == 1*3 mod 5
9  mod 5 == 4 == 3*3 mod 5
27 mod 5 == 2 == 4*3 mod 5
81 mod 5 == 1 == 2*3 mod 5
                 ↑前のmodの結果に3かけていけばよい

modで1になった時、それがp-1回目の乗数だったらおk

ソースコード

int main() {
    istream& in = cin;
    int p;
    in >> p;
    int res = 0;
    // i を試す
    for( int i = 1; i < p; i++ ){
        // j回乗算する
        int n = 1;
        for( int j = 1; j < p; j++ ){
            n *= i;
            // modをとる
            n %= p;
            if( n == 1 ){
                if( j == p - 1 ){
                    res++;
                }else{
                    break;
                }
            }
        }
    }

    cout << res << endl;
}