Codeforces ECR #049 : G. X-mouse in the Campus

勉強になりました。
http://codeforces.com/contest/1027/problem/G

問題

互いに素である整数M,Xが与えられる。
0≦V＜Mに対し、Vに順次Xを掛けmod Mを取ることを繰り返して得られる数列はいくつかのサイクルを成す。
そのサイクル数はいくつか。

解法

GCD(V,M) = gとなるVを考える。GCD(M,X)=1よりGCD(V*X,M) = gなので、VはMとの最大公約数毎に考えればよい。
そこでgを総当たりしよう。これはMの約数を総当たりすればよい。

d=M/gとする。
V=V'*gと置くと、V'にXを掛けmod dを取ってできる数列はいくつのサイクルからなるかという問題になる。
これは一見元の問題と近いが、元の問題ではVとMが互いに素でない場合もあるが、こちらはV'とdが素の場合だけを考えればよい。

オイラーの定理より、V'であり得る値はtotient(d)通りである。
よって、X,dに対し、X^y=1(mod d)となる最小の正整数yを求められれば、サイクルの数はtotient(d)/yとなる。
y自身totient(d)の約数なので、総当たりなどで最小値を求めよう。

ll M,X;
vector<ll> Ds;
vector<pair<ll,int>> Ps;

ll totient(ll v) {
	FORR(p,Ps) if(v%p.first==0) v=v/p.first*(p.first-1);
	return v;
}

ll multpow(ll a,ll b,ll m) {
	ll r=0;
	a%=m;
	while(b) {
		if(b&1) r+=a;
		a<<=1;
		b>>=1;
		if(a>=m) a-=m;
	}
	return r%m;
}
ll modpow(ll a,ll p,ll m) {
	ll r=1;
	while(p) {
		if(p&1) r=multpow(r,a,m);
		a=multpow(a,a,m);
		p/=2;
	}
	return r;
}

ll ord(ll x,ll d) {
	if(x==1) return 1;
	vector<pair<ll,int>> P;
	int i;
	ll t=totient(d);
	ll v=t;
	for(ll a=2;a*a<=v;a++) if(v%a==0) {
		P.push_back({a,0});
		while(v%a==0) P.back().second++, v/=a;
	}
	if(v>1) P.push_back({v,1});
	
	ll ret=t;
	FORR(p,P) {
		int i;
		ll dv=1,t2=t;
		FOR(i,p.second) {
			t2/=p.first;
			if(modpow(x,t2,d)!=1) break;
			ret/=p.first;
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>M>>X;
	
	ll M2=M;
	for(ll d=1;d*d<=M;d++) {
		if(M%d==0) {
			if(d>1) Ds.push_back(d);
			if(d*d!=M) Ds.push_back(M/d);
		}
		if(d>1 && M2%d==0) {
			Ps.push_back({d,0});
			while(M2%d==0) M2/=d, Ps.back().second++;
		}
	}
	if(M2>1) Ps.push_back({M2,1});
	
	ll ret=1;
	FORR(d,Ds) {
		ll phi = totient(d);
		ll o = ord(X%d,d);
		ret += phi/o;
	}
	cout<<ret<<endl;
}

まとめ

こう書かれるとアイデアはシンプルだけど、自分でこれは思いつかないな。