python codefights Count The Black Boxes，建模矩形的对角线

Question

给定一个由单位正方形组成的矩形 (m,n) 的尺寸，输出与矩形对角线相交的单位正方形的数量 - 包括边界和顶点。

我的算法通过循环遍历所有单位正方形来解决这个问题(假设可以绘制我们的对角线从 (0,0) 到 (m,n)

我的算法解决了 10 个测试中的 9 个，但效率太低，无法在给定时间内解决第十个测试。

我对所有提高效率的建议都持开放态度，但以提出特定问题的名义……我似乎在自己的逻辑中脱节了关于添加 break 语句以从过程中删除一些步骤的问题。我的想法是，这应该无关紧要，但它确实会影响结果，我一直无法弄清楚为什么。

所以，有人可以帮助我了解如何插入不影响输出的中断。

或者如何消除循环。我目前正在使用嵌套循环。

所以，是的，我认为我的问题是算法而不是语法。

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 

一些样本，输入/输出

输入:人数:3米:4输出:6

输入:人数:3米:3输出:7

输入:人数:33米:44输出:86

Answer 1

求 G - m 和 n 的最大公约数。

如果 G > 1 则对角线与 G-1 内部顶点相交，接触(不相交)2*(G-1) 单元格.

在这些内部顶点之间有 G 个边互为质数的子矩形 M x N (m/G x n/G)

现在考虑互质M和N的情况。这种矩形的对角线不与除起点和终点外的任何顶点相交。但它必须与 M 条垂直线和 N 条水平线相交，并且在每个交叉点对角线都进入新的单元格，因此它与 M + N - 1 个单元格相交(减去 1 为考虑垂直线和水平线相交的第一个角)

因此使用这些线索并推导出最终解决方案。