我卡在了欧拉计划问题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(1012)也需要太长时间。我认为有必要使用某种筛选算法,在循环所有x < 1012并计算满足h <= w <= 1012, x|(w*h), x != h以及(w-x)|w或(x-h)|x的(w,h)数量。
我认为可能存在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我认为我们应该从某个质数p被分解为x、w、h甚至是x-h的角度入手,然后看看我们可以推断出其他变量的什么。如果这样做得好,也许可以考虑任意k的p^k。