Codeforces #334 Div1 B. Moodular Arithmetic

わかってしまうとすんなり。
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、誰も反応してない…？