Codeforces #210, Division 2, B : Levko and Permutation

問題文

http://codeforces.com/contest/361/problem/B

概要

整数 n, k が与えられる。
1 〜 n の順列であって、 を満たす i の数が k 個であるようなものを一つ出力せよ。
存在しない場合は -1 で示せ。

解法

GCD が 2 以上になる ⇔ 二つの数が互いに素ではない　が言えます。
1 との GCD は 1 なので、制約を満たせる i は最大で n - 1 個です。
従って、n = k のときには解が存在しません。

次に、解がある場合についてです。
まず、1 〜 n が順番に並んだ列について考えます。
このとき、全ての i に関して、i と は共通の約数 i を持つので、1 以外の i については互いに素ではありません。
ところで、互いに素 - Wikipedia によると、連続する二つの整数は互いに素です。
1 〜 m の範囲を一つ回転すると、1 と m のペアを除いて添字と値の差は 1 になるので、互いに素ではなくなります。
1 と m のペアについても、1 との GCD は 1 なので互いに素ではなくなります。
まとめると、1 から n が順に並んだ列を作ってから、末尾の k 個を除いた範囲を一つ回転することで、目的の列が得られます。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, k;
	cin >> n >> k;

	if ( k == n )
	{
		cout << -1 << endl;
		return 0;
	}

	VI as( n );
	iota( ALL( as ), 1 );
	rotate( as.begin(), as.begin() + 1, as.end() - k );
	
	REP( i, 0, n )
	{
		cout << as[i] << ( i + 1 < n ? ' ' : '\n' );
	}
	cout << flush;

	return 0;
}