Diagonal Cut
Time limit1sMemory limit1024 MB
Count the grid cells that a diagonal from one corner to the opposite corner splits into two equal-area halves, given dimensions up to 10^18.
- Level
Medium7 of 10
- Topics
- Math, Number theory, Geometry, Implementation
- Solved
- No attempts yet
Problem
Quido and Hugo are making a chocolate cake. The central ingredient of the cake is a large chocolate bar, lying unwrapped on the kitchen table. The bar is an M × N rectangular grid of chocolate blocks. All of the MN blocks are rectangles of identical shape and size. The chocolate bar is of top quality and the friends want to eat part of it, before the rest is used in the cake.
“OK,” says Quido, “let’s divide the whole bar into two triangular chunks by a straight diagonal cut from its upper-left corner to its lower-right corner. We will then eat all of the blocks which have been cut exactly in half, into two equal-area pieces. You will eat one half and I will eat the other half of each such block. All other blocks, that is, the blocks which are either uncut or cut into two parts of different sizes, will go directly into the cake. Of course, we will make sure the cut is perfectly precise.
Let’s see how much chocolate we get to eat!”
Input
The input consists of two space-separated integers M and N given on a single line, (where 1 ≤ M, N ≤ 10^18). The numbers M and N denote the number of blocks in one column and in one row, respectively, in the chocolate bar.
Output
Print the number of blocks of the chocolate bar which are cut into exactly two pieces of equal area.