ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1139. City Blocks

If you want to know why when gcd(M, N) = 1 Ans is M + N - 1, come in!
Posted by Huang WenHao 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.
Re: If you want to know why when gcd(M, N) = 1 Ans is M + N - 1, come in!
Posted by Rudolf 8 Jan 2016 00:45
and what if gcd(m,n)!= 1 ?? Sorry, can't get you
Re: If you want to know why when gcd(M, N) = 1 Ans is M + N - 1, come in!
Posted by Egor 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.