torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

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

問題概要

 整数 N が与えられる.1, 2, 3, \dots, N の順列をランダムに 1 つ選び p とする.また,関数 f( m ) を次のように定義する.

  • f( 1 ) = 1;
  • f( m ) = p_{ f( m - 1 ) }

 どの順列が p として選ばれていても f( x ) = 1 となる x の内,最小のものを求めよ.
 N \leq 35
 答えは 64 bit 符号付き整数で表現できる.

解法

 まず f について確認しておきます.f の値を p に対するインデックス(1-indexed)と考えると,f( m ) は,f( m - 1 ) が指し示す位置にある値となります.f を 1 回適用する操作は,(直前の操作で求まっている)現在位置 i に対して,if( p_i ) で置き換えることと言えます.f( x ) とは,位置 1 から始めて,そのような遷移を x 回繰り返して得られるインデックスです.f( x ) = 1 となる x についてだけ考えるので,x 回の操作の後,インデックスは初期位置である 1 となります.また,周期性をもつことになるので,(ある順列に対して)f( m ) = 1 ならば,(同じ順列に対して)m の整数倍である km ( k \in \mathbb{ Z }^+) でも f( km ) = 1 となります.
 さて,どのような順列が選ばれたとしても f( x ) = 1 でなければならないので,f の周期としてどのような値が出現し得るかを知らねばなりません.実は,整数 n ( 1 \leq n \leq N ) 対して,2, 3, 4, \dots, n, 1 と並べることで周期 n を作れるので 1 \sim N の整数は全て周期として出現します.すなわち,求めるべき x とは,1 \sim N の全ての倍数の内で最小のもの,すなわち最小公倍数です.
 この問題の場合,答えが 64 bit で表せることが保証されているので,愚直に求めていくことができます.すなわち,次に考慮する値 n に対して,仮(計算途中)の最小公倍数 l\frac{ ln }{ \gcd( l, n ) } で置き換えることで更新していきます.l = 1 から初めて,1 \sim N 全ての値に対して更新をすれば答えが求まります.

コード

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