裏紙

ほぼ競プロ、たまに日記

SRM 652 Div1 Easy - ThePermutationGame

問題

TopCoder Statistics - Problem Statement

問題概要

AliceとBobが次のようなゲームをする。まず、正の整数Nが与えられる。次に、Aliceは正の整数xを選ぶ。最後に、Bobは1~Nの順列pを作成する。

そして、pi番目の要素をp[i]と表すこととし、関数fを次のように定める:

  • f(1) = p[1 ]
  • f(m) = p[f(m-1) ] \ (m \ge 2)

そして、最終的にはf(x)を求める。このとき、Bobがどんな順列を作成したとしてもf(x)=1となるようなxの最小値を求め、その答えを1000000007で割った値を答えよ。

  •  1 \le N \le 100000

イデア

問題文でも少し触れられているが、この関数f写像のような役割を持っている。例えば、N=5P= ( 2,3,1,5,4 )であるような時には次のような図に対応付けられる。

f:id:imulan:20161007184803p:plain

p[1 ] = 2であり、図では頂点1から頂点2へ移動する辺に対応しているのが分かる。そして、何個かグラフを描いてみると簡単に気づけるが、このグラフはPが順列であるという性質上、各頂点に入る辺と各頂点から出る辺はそれぞれ1つずつになることになる。つまり、このN頂点の有向グラフがいくつかの単純な閉路で構成されることになる。

そして、今スタート地点は1なので、頂点1を含む閉路に注目したい。Bobは任意の順列を作成することが出来るので、あり得る閉路の大きさは1,2,3, ... , Nとなる。つまり、求めたいxの最小値はこのN個の数の最小公倍数であるということになる。しかしながら、剰余を取っていかねばならないので単純にLCMを計算していくのはできない。そこで、別の方針で1~Nまでの最小公倍数を求めていく。

まず、N以下の素数を列挙しておく。そして、求まった各素数zに対して、求めたい最小公倍数の中にzは素因数として何個入っているかを考えてみる。これは簡単に求められ、z^n \le Nを満たす最大のnになる。

素数に対してz^nをかけ合わせたものを答えとして出力すれば良い。

実装(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;
    }
};