項目歐拉數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)。顯然，新的矩形區域與舊的矩形區域相同。

這是足夠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。我很幸運地讀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（w，h）滿足以下條件：計算有多少（w，h）滿足h（其中x是最大值） ，x！= h和（wx）| w或（xh）| x。

我認爲一個O（n ^2/3）算法必須是可能的......但我被卡在這裏！

---

編輯：我沒有訪問該論壇，因爲我無法去解決它。這就是我尋求幫助的原因。我已經完成了大多數其他問題，現在想要解決這個問題！

編輯2：我認爲考慮素因素的區域是一個死衚衕。這是因爲有不同的領域。具有素數區域的矩形有0個解，具有半素性區域的矩形如果其中一個素數是2，則有1個解，否則它們有0個解。但是，單獨計算所有半解的解決方案將需要很長的時間，因爲我們需要計算所有質數p，使得2 * p 24這是不可行的。

編輯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 <ħ< N + 1，X = H，最大值（H，X /小時）<瓦特< N + 1，X |！WH和XH |小時。

我認爲一些素數p分爲X，W，我們應該假定啓動H或甚至x-H，然後看看我們可以推導出其他變量。如果這樣做效果很好，那麼可以考慮任意k的p ^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是不可行的，但也許這種算法可以發現在某些時候解析解。如果不是所設定的字符數量，這將是可行的。也許可以通過這種方式找到重複的點。

這可能是死路一條，但它仍然很酷了Python，可用於標記和使用的算法:)

在你身邊的任何進展工作？