Codeforces 194B - B. Square

194B - B. Square

• 左下隅からスタートして、はじめて4隅に止まるのは何ステップ目だろうか。
• 小さいサイズで試してみる。
• 正方形のサイズを n とすると、
  • n = 1 のときは、1 ステップ目で四隅にはじめて到達する
  • n = 2 のときは、2 ステップ目
  • n = 3 のときは、3 ステップ目
  • サイズが n のときは n ステップ目で四隅にはじめて到達する。サイズ n に対して、n+1 だけ進むのだから、n で割った余りを考えれば当然だ。
• n ステップ目で 4 隅のうちのどこにいるかは進んだ距離から求めることが出来る(進む距離は n*(n+1))。
• n*1, n*2, n*3, … と順番に元の位置に戻ったかどうかを調べればよい。

calc :: Integer -> Integer
calc n = head [i*n+1 | i <- [1..], ((n+1)*n*i) `mod` (n*4) == 0]

putLs [] = return ()
putLs (x:xs) = do putStrLn x
                  putLs xs

main = do s <- getLine
          t <- getLine
          putLs $ map (\a -> show $ calc (read a :: Integer)) $ words t

はまったこと。

• `mod`と +, - の演算子の優先順位ではまった。

Prelude> 9+1 `mod` 3
10
Prelude> 9*1 `mod` 3
0