python codefights Count The Black Boxes, modeling the diagonal of a rectangle

Question

Given the dimensions of a rectangle,(m,n), made up of unit squares, output the number of unit squares the diagonal of the rectangle touches- that includes borders and vertices.

My algorithm approaches this by cycling through all the unit squares(under assumption that can draw our diagonal from (0,0) to (m,n)

My algorithm solves 9 of 10 tests, but is too inefficient to solve the tenth test in given time.

I"m uopen to all efficiency suggestions, but in the name of asking a specific question... I seem to be having a disconnect in my own logic concerning adding a break statement, to cut some steps out of the process. My thinking is, this shouldn't matter, but it does affect the result, and I haven't been able to figure out why.

So, can someone help me understand how to insert a break that doesn't affect the output.

Or how to eliminate a loop. I"m currently using nested loops.

So, yeah, I think my problems are algorithmic rather than syntax.

def countBlackCells(m, n):
    counter=0
    y=[0,0]
    testV=0
    for i in xrange(n): #loop over m/x first
        y[0]=float(m)/n*i
        y[1]=float(m)/n*(i+1)
        #print(str(y))
        for j in xrange(m): #loop over every n/y for each x
            if((y[0]<=(j+1) and y[0]>=j) or (y[1]>=(j) and y[1]<=j+1)):#is                min of line in range inside teh box? is max of line?
                counter+=1
                #testV += 1

            else: pass #  break# thinking that once you are beyond the line in either direction, your not coming back to it by ranging up m anymore. THAT DOESN"T SEEM TO BE THE CASE
        #tried adding a flag (testV), so that inner loop would only break if line was found and then lost again, still didn't count ALL boxes. There's something I'm not understanding here. 
    return counter 

Some sample, input/output

Input: n: 3 m: 4 Output: 6

Input: n: 3 m: 3 Output: 7

Input: n: 33 m: 44 Output: 86

Answer 1

Find G - the greatest common divisor of m and n.

If G > 1 then diagonal intersects G-1 inner vertices, touching (not intersecting) 2*(G-1) cells.

And between these inner vertices there are G sub-rectangles with mutually prime sides M x N (m/G x n/G)

Now consider case of mutually prime M and N. Diagonal of such rectangle does not intersect any vertex except for starting and ending. But it must intersect M vertical lines and N horizontal lines, and at every intersection diagonal enters into the new cell, so it intersects M + N - 1 cells (subtract 1 to account for the first corner where both vertical and horizontal lines are met together)

So use these clues and deduce final solution.