torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 594, Division 2, Level 1 : FoxAndClassroom

概要

H * W の机が置かれた教室があり、最初は好きな席に座ることができる。
その後、週毎に次のように席を変える。
 現在の座席の位置を ( y, x ) とすると ( ( y + 1 ) MOD H, ( x + 1 ) MOD W ) に移動する
十分な時間をかけたとき、全ての座席に座ることができるかどうか求めよ。

解法

GCD( H, W ) が 1 のとき可能、そうでなければ不可能です。
証明できない程度の数学力です。

コード

class FoxAndClassroom
{
public:
	string ableTo( int n, int m )
	{
		return __gcd( n, m ) == 1 ? "Possible" : "Impossible";
	}
};