問題一覧 > 通常問題

No.84 悪の算盤

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 217
作問者 : LayCurseLayCurse
2 ProblemId : 166 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:46:58

問題文

太郎君はそろばんが苦手で、特に、珠の位置によってその珠が表す数が違うことに納得ができなかった。
そこで、太郎君は二次元の各場所に珠があるかどうかのみで表す整数を決めるような新しい方法を考えだした。
以下ではわかりやすさを優先して、抽象化して説明する。

\(R\) 行 \(C\) 列のマス目があり、各マスには珠があるかどうかである。
珠は合計で \(RC-1\) 個ある。つまり、\(1\) マスだけ珠がないマスが存在する。
各盤面に対して \(0\) 以上の整数を対応させる。
また、対応させる整数の最大値を \(K\) とすると、\(0\) 以上 \(K\) 以下の全ての整数に対して対応する盤面が存在しなければいけない。
ただし、そろばんはひっくり返すことはできないが、回転することができるため、回転して一致する盤面に対しては同じ整数を対応させなくてはいけない。
\(R\) と \(C\) が与えられるので、対応させる整数の最大値 \(K\) の最大値を求めるプログラムを書いてください。

入力

\(R\) \(C\)

\(1 \leq R, C \leq 10^9\)

出力

\(K\) の最大値を \(1\) 行に出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2 3
出力
2

合計 \(6\) 個の盤面が存在し、珠のあるセルを*で、無いセルを.で表すと、各盤面を以下のように整数と対応させることができる。
ここで、整数 \(0\) に対応する \(2\) つの盤面は \(180\) 度回転することで一致するので、この \(2\) つの盤面は同じ整数に対応させなければいけない。

0    0    1    1    2    2
***  .**  *.*  ***  **.  ***
**.  ***  ***  *.*  ***  .**
サンプル2
入力
1 1
出力
0

盤面がそもそも \(1\) つしか存在せず、その盤面を整数 \(0\) に対応させなくてはいけません。

サンプル3
入力
123456789 987654321
出力
60966315556317634

答えは \(32\) ビット整数型に収まらないことがありますので注意してください。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。