###
**Problem**

Imagine a white rectangular grid of

`n`

rows and `m`

columns divided into two parts by a diagonal line running from the upper left to the lower right corner. Now let's paint the grid in two colors according to the following rules:- A cell is painted black if it has at least one point in common with the diagonal;
- Otherwise, a cell is painted white.

Count the number of cells painted black.

###
**Solution**

http://www.cut-the-knot.org/Curriculum/Geometry/LineThroughGrid.shtml#solution explains the solution very well.

Here is the code that solves the problem:

int gcd(int n, int m){ while (m) { int temp = n; n = m; m = temp%m; } return n; } int countBlackCells(int n, int m) { if (n == m) return (n + 2*(n-1)); if (n == 1 or m==1 ) return n*m; return n + m -gcd(n, m) + (gcd(n, m)-1)*2; }

I'm truly enjoying the design and layout of your site. It's a very easy on the eyes which makes it much more pleasant for me to come here and visit more often. Did you hire out a designer to create your theme? Superb work! Software de Activos Fijos

ReplyDelete