欧拉项目第338号

Question

我在Project Euler的第338题上遇到了困难。到目前为止，我做了这些……

我们用宽度和高度分别为x和y的矩形表示为(x,y)。要形成新的矩形，你可以考虑沿着对角线切割出一种阶梯形状（问题描述中有说明），这个切割有d步。但要形成新的矩形，必须满足以下条件：d|x，并且(d-1)|y或(d+1)|y。然后新的矩形变成(x/d*(d-1), y/(d-1)*d)或(x/d*(d+1), y/(d+1)*d)。显然，新矩形的面积和旧矩形的面积是一样的。

这样就足够确认G(10)=55和G(1000)=971745，通过遍历所有相关的d，并将所有新矩形添加到一个集合中，注意只计算一次(x,y)和(y,x)。

这个方法的主要问题是，可能会有两种不同的方式来形成一个新的矩形。例如，(9,8)可以通过d=3变成(6,12)和(12,6)，而且d-1或d+1都能整除y。再比如，(4,4)可以通过d=2变成(2,8)和通过d=1变成(8,2)。

后来我很幸运地读到了这篇博客。它通过寻找其中一条边，消除了检查重复的需要。

def F(w, h):
    if w&1 and h&1: return 0
    if w<h: w,h = h,w

    r = 0
    x = 1
    while x**2 <= w*h:
        if (w*h)%x!=0 or x==h:
            x += 1
            continue

        if w%(w-x)==0 or x%(x-h)==0:
            r += 1

        x += 1

    return r

def G(N):
    s = 0
    for w in range(1, N+1):
        for h in range(1, w+1):
            s += F(w,h)

    return s

不过，计算G(1012)所需的时间会非常长，无论F有多快。我认为有必要使用某种筛选算法，遍历所有x < 1012，计算满足h <= w <= 1012的(w,h)的数量，且满足x|(w*h)、x != h和(w-x)|w或(x-h)|x。

我觉得应该能实现一个O(n2/3)的算法……但我在这里卡住了！

---

编辑：我无法访问论坛，因为我无法解决这个问题。这就是我寻求帮助的原因。我已经完成了其他大部分问题，现在想解决这个问题！

编辑 2：我觉得通过素因子考虑面积是个死胡同。因为有1024种不同的面积。素数面积的矩形没有解，半素数面积的矩形如果其中一个素数是2则有1个解，否则没有解。但单独计算所有半素数解会花费太长时间，因为我们需要计算所有的素数p，使得2*p < 1024，这并不可行。

编辑 3：我简化了代码：

def G(N):
    s = 0
    for x in range(1, N):
        for h in range(1, N+1):
            if x==h: continue
            for w in range(max(h, x**2//h), N+1):
                if (w*h)%x==0 and x%(w-x)==0 and x%(x-h)==0:
                    s -= 1

    for x in range(1, N):
        for h in range(1, N+1):
            if x==h: continue
            for w in range(max(h, x**2//h), N+1):
                if (w*h)%x==0 and w%(w-x)==0:
                    s += 1

    for x in range(1, N):
        for h in range(1, N+1):
            if x==h: continue
            for w in range(max(h, x**2//h), N+1):
                if (w*h)%x==0 and h%(x-h)==0:
                    s += 1

    return s

不过，我觉得拆解暴力破解的代码是行不通的。记住，只需计算每个子问题的解(x, w, h)的数量就足够了。最后的求和将有以下约束条件：0 < x < N，0 < h < N+1，x!=h，max(h, x2/h) < w < N+1，x|wh和x-h|h。

我觉得我们应该假设某个素数p能整除x、w、h，甚至x-h，然后看看我们能推导出其他变量什么。如果这样有效，也许可以考虑pk，对于任意的k。

Answer 1

我还没有找到解决办法，但有一些有趣的关于Python的事情。我发现Python可以作为一个方便的工具来表示算法！基本上，我写了一个和你类似的程序，然后开始在逻辑上对这个程序进行变换，但结果保持不变。我得到了

def order(x,y):
    if x>=y:
        return (x,y)
    else:
        return (y,x)

N=1000
num=set()
for n in range(1, N+1):
    for a in range(1,N//n+1):
        for b in range(1,N//(n+1)+1):
            if a==b: continue
            num.add((order(a*n,b*(n+1)), order(b*n,a*(n+1))))

print(N, len(num))

显然，暴力破解或者简单地循环10^12次是不可行的，但也许通过这个算法，某个时候可以找到一个封闭形式的表达式。如果不是因为num的集合特性，这样做是可以的。也许可以通过这种方式找到重复的点。

这可能是个死胡同，但Python能用来表示和处理算法，还是挺酷的 :)

你那边有什么进展吗？