项目欧拉编号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)可以转换为(6,12)和(12,6)使用d=3和使用d-1或者d+1分割y.或者分别(4,4)转换为(2,8)和(8,2)使用d=2和转换的另一个示例d=1.

那时我很幸运地阅读了这篇博客文章.它不需要通过搜索其中一个边来检查重复项.

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 ¹²计算有多少(w,h)满足h <= w <= 10 ¹²,x |(w*h),x!= h和(wx)| w或(xh)| x.

我认为O(n ^2/3)算法必须是可能的......但我被困在这里!

---

编辑:我无法访问论坛,因为我无法解决它.这就是我寻求帮助的原因.我已经完成了大多数其他问题,现在想解决这个问题!

编辑2:我认为按主要因素考虑区域是一个死胡同.那是因为有10 ^个不同的区域.具有素数区域的矩形具有0个解,具有半素面积的矩形具有1个解,如果其中一个素数为2,否则它们具有0个解.但是,单独计算所有半素数解决方案需要花费太长时间,因为我们需要计算所有素数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 <x <N,0 <h <N + 1,x!= h,max(h,x ²/h)<w <N + 1,x | wh和xh | h .

我认为我们应该首先假设一些素数p除以x,w,h或甚至xh,然后看看我们可以推断出其他变量.如果效果很好,可以将p ^k视为任意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 可以用于表示法和使用算法仍然很酷:)

你这边有进展吗？