TopCoder, Single Round Match 652, Division 2, Level 2 : ThePermutationGameDiv2

問題文

　http://community.topcoder.com/stat?c=problem_statement&pm=13679&rd=16316[

問題概要

　整数 が与えられる． の順列をランダムに 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;
	}
};