問題概要
整数 が与えられる. の順列をランダムに 1 つ選び とする.また,関数 を次のように定義する.
- ;
どの順列が として選ばれていても となる の内,最小のものを求めよ.
答えは 64 bit 符号付き整数で表現できる.
解法
まず について確認しておきます. の値を に対するインデックス(1-indexed)と考えると, は, が指し示す位置にある値となります. を 1 回適用する操作は,(直前の操作で求まっている)現在位置 に対して, を で置き換えることと言えます. とは,位置 1 から始めて,そのような遷移を 回繰り返して得られるインデックスです. となる についてだけ考えるので, 回の操作の後,インデックスは初期位置である 1 となります.また,周期性をもつことになるので,(ある順列に対して) ならば,(同じ順列に対して) の整数倍である でも となります.
さて,どのような順列が選ばれたとしても でなければならないので, の周期としてどのような値が出現し得るかを知らねばなりません.実は,整数 対して, と並べることで周期 を作れるので の整数は全て周期として出現します.すなわち,求めるべき とは, の全ての倍数の内で最小のもの,すなわち最小公倍数です.
この問題の場合,答えが 64 bit で表せることが保証されているので,愚直に求めていくことができます.すなわち,次に考慮する値 に対して,仮(計算途中)の最小公倍数 を で置き換えることで更新していきます. から初めて, 全ての値に対して更新をすれば答えが求まります.
コード
using LL = long long; #define REP2( i, n ) REP3( i, 0, n ) #define REP3( i, m, n ) for ( int i = ( int )( m ); i < ( int )( n ); ++i ) #define GET_REP( a, b, c, F, ... ) F #define REP( ... ) GET_REP( __VA_ARGS__, REP3, REP2 )( __VA_ARGS__ ) class ThePermutationGameDiv2 { public: long long findMin( int N ) { LL res = 1; REP( i, 2, N + 1 ) { res = res / __gcd( res, LL( i ) ) * i; } return res; } };