ACM 1139. City Blocks / Городские кварталы

 First let us answer the following question : how many coordinates will the helicopter pass which have a natural coordinates. We need to look at the geometrical illustration.

Have a look at the picture below.

So, this is our coordinate system and the points (0,0) and (9,6) are connected, what are all the coordinates which have natural coordinates and the red line passes over them those are (0,0) (3,2) (6,4) (9, 6) . I think you already see the pattern here but let's try proving it. So we can build a right angle triangle with the points (0,0) (9,0) and (9,6) , we will call that triangle 1. And let's build another one with the points (0,0) (0,6) (6,4) we will call that triangle 2. So, if we compare the triangles 1 and 2 we can say that they are similar (due to equal angles) which means that their sides are   multiples. A Conclusion  all the multiples of the pair (9,6) (to the one which we connected the initial (0,0) point) are vertexes of such triangles, => are the points which have natural coordinates which our line crosses. Let's have a little case which is (0,0) to (2,3). (2,3) do not have any multiples so there is no point with natural coordinates on the way. which means that the line crosses all the available vertical lines and all the available horizontal lines separately. The total number of those is 2+3-1=4 which gives us the first idea of the answer which is N+M-1. If there are natural coordinated points then our task is divided into sub tasks, in out case we have 3 different sub-tasks each has the same answer. For finding the number of natural coordinates on the way we need to find the GCD (greatest common divisor). In this case it would be (M/GCD+N/GCD-1) * GCD which gives the answer of M+N-GCD.