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