Discussion @ 1139. City Blocks @ Timus Online Judge

Huang WenHao If you want to know why when gcd(M, N) = 1 Ans is M + N - 1, come in! [2] // Problem 1139. City Blocks 21 Apr 2006 21:17

If the plane fly across a edge and it will produce a point then produce a new block so the answer add one.
If gcd(M, N) = 1, it means there is no situation that the plane fly across the crossroads.
See from left to right it produce M point and see from north to south it produce N point,
but one is calculate twice, so there are M + N - 1 points and Ans is M + N - 1.

Rudolf Re: If you want to know why when gcd(M, N) = 1 Ans is M + N - 1, come in! [1] // Problem 1139. City Blocks 8 Jan 2016 00:45

and what if gcd(m,n)!= 1 ?? Sorry, can't get you

Egor Re: If you want to know why when gcd(M, N) = 1 Ans is M + N - 1, come in! // Problem 1139. City Blocks 30 Oct 2016 22:52

Rudolf wrote 8 January 2016 00:45

and what if gcd(m,n)!= 1 ?? Sorry, can't get you

Reduce to smaller problem (m / gcd(m,n), n / gcd(m,n)) and then use it to solve the original problem.

Discussion of Problem 1139. City Blocks