#45120: 直接印答案就沒意思了


sam851015@gmail.com (多挖鼻孔有益身心健康)

學校 : 臺中市立惠文高級中學
編號 : 277705
來源 : [123.192.228.253]
最後登入時間 :
2025-03-11 12:39:29
d214. What's the next number? -- Project Euler | From: [123.192.228.253] | 發表日期 : 2025-01-09 22:51

對,我就是在說其他解題報告

都已經在寫程式了,那還是動手讓程式算吧

 

只要條件設定的夠好,暴力解也不會 TLE

 

Tn=n(n+1)2

Pn=n(3n1)2

Hn=n(2n1)

 

Tt=Pp=Hh 的解,其中 t,p,h 均為正整數

 

簡化下面這兩個等式

Tt=Hh=t(t+1)2=h(2h1)

Pp=Hh=p(3p1)2=h(2h1)

 

可得下面的結果(忽視過程,大意就是套一元二次方程式的公式解)

t=2h1

p=1+48h224h+16

 

已經盡量簡化了,如果還有更簡單的歡迎提出來(其實也不是我自己算的,我是丟給chatGPT讓他幫我簡化)

 

透過上面的關係式,我們可以觀察到 Hexagonal 其實就是 Triangle 的子集,Hexagonal 的所有數字都會在 Triangle 中出現。

這是好消息,意味著我們不需要窮舉 Triangle 的值,

隨便輸入一個 Hexagonal 的數字,必然可以在 Triangle 中找到一模一樣的數字。

我們只需要找 Pentagonal 中有沒有和 Hexagonal 一樣的數字就可以了

 

透過上面的關係式,我們也可以不用窮舉 Pentagonal 的值,

我們知道在 Pn=n(3n1)2 中, n 必為正整數

 

這代表 p=1+48h224h+16p 也必須是正整數

所以根號裡面的東西就只能是完全平方數,這樣才可能有解

 

有以上的線索後就可以暴力解了

窮舉 h 的值,從 144 後開始(題目說的),尋找符合條件的 p 

 

 
#45121: Re: 直接印答案就沒意思了


sam851015@gmail.com (多挖鼻孔有益身心健康)

學校 : 臺中市立惠文高級中學
編號 : 277705
來源 : [123.192.228.253]
最後登入時間 :
2025-03-11 12:39:29
d214. What's the next number? -- Project Euler | From: [123.192.228.253] | 發表日期 : 2025-01-09 23:05

參考答案: gist 連結

 

 

 

 
ZeroJudge Forum