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; }