No.84 Evil Abacus
タグ : / 解いたユーザー数 277
作問者 :
LayCurse
Problem Statement
Taro is bad at the abacus, and in particular, he could not accept that the number a bead represents differs depending on its position.
So Taro came up with a new method in which the represented integer is determined solely by whether or not there is a bead at each location in two dimensions.
Below, prioritizing clarity, the method is described in abstract terms.
There is a grid with \(R\) rows and \(C\) columns, and each cell either has a bead or does not.
There are \(RC-1\) beads in total. That is, there is exactly \(1\) cell with no bead.
Assign an integer greater than or equal to \(0\) to each board.
Also, letting \(K\) be the maximum of the assigned integers, for every integer between \(0\) and \(K\), inclusive, there must exist a board assigned to it.
However, although the abacus cannot be flipped over, it can be rotated, so boards that coincide under rotation must be assigned the same integer.
Given \(R\) and \(C\), write a program that finds the maximum possible value of \(K\), the maximum of the assigned integers.
Input
\(R\) \(C\)
\(1 \leq R, C \leq 10^9\)
Output
Print the maximum value of \(K\) on \(1\) line.
Print a newline at the end.
Sample
Sample 1
Input
2 3
Output
2
There are \(6\) boards in total. Representing cells with a bead by * and cells without a bead by ., each board can be assigned an integer as follows.
Here, the \(2\) boards assigned the integer \(0\) coincide under a \(180\)-degree rotation, so these \(2\) boards must be assigned the same integer.
0 0 1 1 2 2 *** .** *.* *** **. *** **. *** *** *.* *** .**
Sample 2
Input
1 1
Output
0
There is only \(1\) board in the first place, and that board must be assigned the integer \(0\).
Sample 3
Input
123456789 987654321
Output
60966315556317634
Note that the answer may not fit in a \(32\)-bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。