欧拉项目338号

Question

我卡在了欧拉计划问题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)。显然，新矩形的面积与旧矩形相同。

通过循环遍历所有相关的d，并将所有新矩形添加到一个集合中，小心地只计算(x,y)和(y,x)一次，就足以证实G(10)=55和G(1000)=971745。

这种方法的主要问题在于可以用两种不同的方式创建新的矩形。例如，(9,8) 可以通过 d=3 和 y 被 d-1 或 d+1 整除来转换为 (6,12) 和 (12,6)。或者另一个例子是 (4,4) 分别通过 d=2 和 d=1 转换为 (2,8) 和 (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

即使F速度再快，解决G(10¹²)也需要太长时间。我认为有必要使用某种筛选算法，在循环所有x < 10¹²并计算满足h <= w <= 10¹², x|(w*h), x != h以及(w-x)|w或(x-h)|x的(w,h)数量。

我认为可能存在O(n^2/3)的算法...但我卡在这里了！

---

编辑：由于我无法解决问题，因此无法访问论坛。这就是为什么我请求帮助。我已经完成了大多数其他问题，现在想解决这个问题！

编辑2：我认为考虑质因数的面积是一条死路。这是因为有10²⁴个不同的面积。具有质数面积的矩形没有解，具有半质数面积的矩形如果其中一个质数是2，则有1个解，否则它们没有解。但仅计算所有半质数解需要太长时间，因为我们需要计算所有质数p，使得2*p < 10²⁴，这是不可行的。

编辑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

我认为我们应该从某个质数p被分解为x、w、h甚至是x-h的角度入手，然后看看我们可以推断出其他变量的什么。如果这样做得好，也许可以考虑任意k的p^k。

- ForeverStuck

---

如果你卡住了，可以尝试另一个题目。正如该网站所说："如果你无法解决它，那就是无法解决它！" - hammar

你可能还想在math.stackexchange.com上提问。 - agf

提交你在欧拉计划中的解答后，你将获得该问题的留言板访问权限；有可能已经有人找到了最优算法。 - Edwin

另一种思考这个问题的方式是从数字的质因数角度来看待。以9 * 4为例，你有33和22，当然可以有三种不同的排列方式，即3和322、2和332、32和32。计算独特排列是否更快？我不知道这种方法是否可行，但这是解决问题的另一种方式。祝好运。 - Jackson

我不明白为什么会有超过10个的投票。Project Euler 是关于自己解决问题的。 - dfens

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可以用于符号表示和算法处理 :)

你这边有进展吗？

- Gere