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

Question

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

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

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

我对所有提高效率的建议持开放态度，但以提出特定问题的名义......我似乎在我自己的逻辑中脱节了关于添加 break 语句的问题，以减少一些步骤process.我的想法是，这个应该没关系，但是确实影响了结果，一直没弄清楚为什么。

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

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

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

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

一些样本，input/output

输入：人数：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 以考虑垂直和水平的第一个角线相交）

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

Answer 2

我用 math.gcd() 解决了 python 中的问题。

def countBlackCells(n, m):
    return m+n+math.gcd(m,n)-2

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

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

python

algorithm

geometry

nested-loops