わかってしまうとすんなり。
http://codeforces.com/contest/603/problem/B
問題
素数PとP未満の非負整数Kが与えられる。
f(x)を{0..(P-1)}の整数xを取り{0..(P-1)}の範囲の整数を返す関数とする。
f(k*x mod P) = k*f(x) mod Pを満たすfの組み合わせはいくつあるか。
解法
K=0,1はコーナーケースとして別に処理しよう。
- K=0の時
- f(0)=0、それ以外はなんでも良いので、解はP^(P-1)
- K=1の時
- f(x)はなんでも良いので解はP^P
K>=2の時を考える。
f(K*0%P)=K*f(0)%Pよりf(0)=0は確定である。
ここでf(x)=yとする。
題意より(mod Pは省略して) f(k*x)=y*f(x)なので、k^n % P == 1となる最小の正整数nに対してはf(k^n*x)=k^n*f(x)=f(x)である。
よってf(x)を定めると、f(k*x)、f(k^2*x)、…f(k^(n-1)*x)も一意に定まる。
f(x)は0~(P-1)任意に決められ、それによってf(x)がn個分定まる。
よって全体では(P-1)/n個の要素を任意に決められると考えられ、P^((P-1)/n)が解。
nは適当に乗算すれば求められる。
ll P,K; ll mo=1000000007; void solve() { int i,j,k,l,r,x,y; string s; cin>>P>>K; ll ret=1; if(K<=1) { FOR(i,P-(K==0)) ret=ret*P%mo; } else { ll cur=1; for(i=1;i<P;i++) { cur=cur*K%P; if(cur==1) break; } FOR(x,(P-1)/i) ret=ret*P%mo; } cout<<ret<<endl; }
まとめ
本番無駄にUnion-Findとかしてループの数求めてしまった。
タイトルの"Moo"dular、誰も反応してない…?