kmjp's blog

競技プログラミング参加記です

TopCoder SRM 652 Div1 Easy ThePermutationGame、Div2 Medium ThePermutationGameDiv2

またUnratedか…。まぁMedium解けてない時点で大幅レート上昇はなのでいいけど。
http://community.topcoder.com/stat?c=problem_statement&pm=13229
http://community.topcoder.com/stat?c=problem_statement&pm=13644

問題

1~Nのpermutationである配列p[i]がある。
最初k=1からスタートし、k=p[k]による値の更新をx回繰り返すとk=1に戻るとする。

pの内容がどんなであれ、k=1に戻れる最小のxを求めよ。

解法

pの内容によって、k=1に戻る周期が1~Nの任意の値となるようにできる。
よって求めるxは1~Nの最小公倍数。

最小公倍数には1~Nを順に素因数分解して、新規の素数mが見つかるたびにm^l≦Nとなる範囲でmを掛けてもよいし、各値の素因数分解後における素因数の乗数の最大値を求めて、最後に掛け合わせてもよい。
以下のコードは後者。

Div2の場合10^9+7の剰余をとらないようにすること。

ll mo=1000000007;

map<ll,int> enumdiv(ll n) {
	map<ll,int> V;
	if(n==1) V[1]=1;
	else {
		for(ll i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
		if(n>1) V[n]++;
	}
	return V;
}

class ThePermutationGame {
	public:
	int findMin(int N) {
		int i;
		map<ll,int> M;
		
		for(i=2;i<=N;i++) {
			map<ll,int> MM=enumdiv(i);
			ITR(it,MM) M[it->first]=max(M[it->first],it->second);
		}
		
		ll ret=1;
		ITR(it,M) {
			FOR(i,it->second) ret=ret*it->first%mo;
		}
		return ret;
		
	}
}

まとめ

割と典型っぽいのによくSRMででたなぁ。