Well, this is for those who didnt get the method.
Consider N: no of rows of blocks M: no of columns of the blocks (N+1 and M+1 are the input).
Crosspoint here refers to a point where a horizontal and a vertical line meet.

For each line that the plane intersects, a new block is introduced. Consider the south western most point also as one such point. No of horizontal lines intersected=N. No of vertical lines intersected=M. But the southwestern most point has been counted twice and it introduces the same first block.
If gcd(M,N)==1, there is no intermediate point where the line passes over a crosspoint. Hence no. of blocks = M+N-1.
If gcd(M,N)!=1, the whole grid can be split horizontally at
the points where the line passes over a crosspoint and each of them can be considered separately with that cross point as the south westernmost point of the subproblem. There are gcd(M,N) such points. Say a=gcd(M,N). Then in each subproblem  the line flies over M/a+N/a-1 blocks. Totally the line flies over a*(M/a+N/a-1) blocks. ie. M+N-a blocks.

Edited by author 29.11.2007 02:42

Edited by author 26.09.2015 00:39

Or you can do it simply by tracing error:

int filled_pixels = 0;
long long error = 0;
for (int x = 1; x <= dx; x++)
{
  filled_pixels++;

  error += dy;
  if (error >= dx)
  {
    error -= dx;
    if (error != 0)
      filled_pixels++;
  }
}

The code is incomplete, but the idea should be clear. We need to maintain error. When we exceed this threshold, that means we have crossed horizontal line.

M+N-a works in any case, even if gcd(M,N)=1, right?