ProjectEuler 652 - Solution

這大概是我題目讀得最久的一次。花了將近一個小時還是讀不懂這兩句。

$\quad \, \, \, \, g(m_1,n_1)=g(m_2,n_2)$ if any integers $a,b,e,f$ fulfilling 1. or 2. can be found

and $\, g(m_1,n_1) \ne g(m_2,n_2)$ if no integers $a,b,e,f$ fulfilling 1. or 2. can be found

最後發覺時間不能再耗下去，決定從題目給的測資下手，$D(5)=13$, $D(10)=69$, $D(100)=9607$ 且 $D(10000)=99959605$

然後靈機一動，想到會不會是指那個？試了一下果然是....
原來$D(N)$是指在$2\le m, n\le N$的情況下${log}_mn$不同值的個數。例如${log}_22$跟${log}_33$的值都是1，因此視為相同。

很快的寫了程式驗證一下，果然是 $D(5)=13$, $D(10)=69$, $D(100)=9607$ 且$D(10000)=99959605$


這樣咻的一下子已經一小時過去了，忽然覺得肚子痛痛der，原來是太早起來，宿便還沒清，話說回來，這題目也讓我感覺一肚子大便，就去拉大便了，拉完出來一看，已經4個人解出來了，看來不是很難的題目嘛。

拉完大便之後忽然覺得肚子很餓，就去買早餐了，買完早餐吃完早餐後已經是7點40幾分了。一個小時又40幾分後才弄清楚題目在問什麼，已經破了我閱讀題目弄清題意的時間紀錄了。然後就開始用紙筆算了一下，好像不是很難，很快就推導出公式。然後照著公式implement，經過一番debug後得出D(10000)=99959605，此時差不多已經過了4小時多一點。然後直接跑D(10¹⁸)，很快就跑出來，程式執行時間非常快，不到0.1秒，結果直接告訴我答案不對。

不知道是哪裡錯了？檢查了半天，好像是overflow的問題，我的程式需用到一個函式LL solve(LL x, int p) ，這個函式會傳回在$n^p \le x$情況下的最大的n值(n為正整數)，當x接近10¹⁸時運算就發生溢位了。結果這個bug解了快一個小時，就後以5小時10分拿到第20名，我的目標只有前20名而已，算是達標了。

雖然紀錄上是給出5小時10分，但扣掉題意不清造成的時間浪費，實際上只花了3小時多在解這道題目。