SRM604Div1Easy
問題
無限の平面を考える。k=0から始まり、四方向のどれかに必ず毎回移動するロボットが存在する。このロボットは(x, y)に到達することが可能か求めよ。
解法
到達可能な場合を考える。この時、(x,y)は以下となる。
は+,-の符号を、は0,1を示す。
指数が0の部分を除けば3を共通項として持っているので、必ず割り切れるようになる。指数が0になっている項は、符号が-の場合は余りは2に、+の場合は1となる。この性質を利用し、xとyがゼロになるかを確認する。xとyのどちらかの余りは0になるはずなので、そうならない場合は到達不可能なケースとなる。
計算量