python - 欧拉计划数 338

Question

我卡在了欧拉计划 problem 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 并将所有新矩形添加到集合中，这足以确认 G(10)=55 和 G(1000)=971745注意只计算一次 (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 分别。

然后我很幸运地阅读了this blog post .它消除了通过搜索其中一侧来检查重复项的需要。

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(10¹²) 无论 F 有多快都需要很长时间才能解决。我认为有必要使用某种筛选算法，我们循环遍历所有 x < 10¹² 计算有多少 (w,h) 满足 h <= w <= 10¹², x|(w*h), x != h and (w-x)|w or (x-h)|x.

我认为 O(n^2/3) 算法一定是可行的……但我被困在这里了!

---

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

编辑 2:我认为按主要因素考虑区域是死胡同。那是因为有 10²⁴ 个不同的区域。具有质数区域的矩形有 0 个解，如果其中一个质数为 2，则具有半质数区域的矩形有 1 个解，否则它们有 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 和 x-h|h。

我认为我们应该从一些素数 p 整除 x、w、h 甚至 x-h 的假设开始，然后看看我们可以从其他变量中推断出什么。如果效果很好，可以考虑 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 可以用于符号和算法仍然很酷 :)

你这边有什么进展吗？