概要
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"; } };