SRM 652 Div1 Easy - ThePermutationGame
問題
TopCoder Statistics - Problem Statement
問題概要
AliceとBobが次のようなゲームをする。まず、正の整数が与えられる。次に、Aliceは正の整数を選ぶ。最後に、Bobは~の順列を作成する。
そして、の番目の要素をと表すこととし、関数を次のように定める:
そして、最終的にはを求める。このとき、Bobがどんな順列を作成したとしてもとなるようなの最小値を求め、その答えをで割った値を答えよ。
アイデア
問題文でも少し触れられているが、この関数は写像のような役割を持っている。例えば、でであるような時には次のような図に対応付けられる。
であり、図では頂点から頂点へ移動する辺に対応しているのが分かる。そして、何個かグラフを描いてみると簡単に気づけるが、このグラフはが順列であるという性質上、各頂点に入る辺と各頂点から出る辺はそれぞれ1つずつになることになる。つまり、この頂点の有向グラフがいくつかの単純な閉路で構成されることになる。
そして、今スタート地点はなので、頂点を含む閉路に注目したい。Bobは任意の順列を作成することが出来るので、あり得る閉路の大きさはとなる。つまり、求めたいの最小値はこの個の数の最小公倍数であるということになる。しかしながら、剰余を取っていかねばならないので単純にLCMを計算していくのはできない。そこで、別の方針で~までの最小公倍数を求めていく。
まず、以下の素数を列挙しておく。そして、求まった各素数に対して、求めたい最小公倍数の中には素因数として何個入っているかを考えてみる。これは簡単に求められ、を満たす最大のになる。
各素数に対してをかけ合わせたものを答えとして出力すれば良い。
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second class ThePermutationGame { public: const ll mod=1000000007; const int P=100000; int findMin(int N) { bool prime[P+1]; fill(prime,prime+P+1,true); prime[0]=prime[1]=false; for(int i=2; i<=P; ++i) { if(prime[i]) for(int j=2; i*j<=P; ++j) prime[i*j]=false; } vector<int> p; rep(i,P+1) if(prime[i]) p.pb(i); ll ret=1; rep(i,p.size()) { if(p[i]>N) break; ll mul=p[i]; while(mul*p[i]<=N) mul*=p[i]; mul%=mod; (ret*=mul)%=mod; } return (int)ret; } };