題目連結:
題目大意:
輸入有多列,每列給定一正整數 H (H < 2 ^ 64),代表柏恩的今天最後的心情值。
他今天一開始的心情值為 1 。每喝一杯甜度值為 x 的奶茶,他的心情值會變為原本的 x 倍。
已知他喝了四杯奶茶,且除了第一杯以外每一杯都比前一杯的甜度值多一。
試問根據心情值 H ,柏恩今天喝的四杯奶茶之甜度值依序為何?
範例輸入:
121
25
範例輸出:
2 3 4 5
1 2 3 4
解題思維:
假設第一杯的甜度值為 X,則剩下三杯甜度值依序為 X + 1 、 X + 2 、 X + 3。
根據題意,則我們可以得到以下方程式:
X(X + 1)(X + 2)(X + 3) = H
如果你會解(或是直接用網路上的數學工具)一元四次方程式,且根據 X 應為正數,則可以看到
X = (sqrt(4 * sqrt(H) + 5) - 3) ÷ 2
其中 sqrt() 為求平方根之值。
如果完全不知道公式解(應該沒什麼人記得住一元四次方程式的公式解才對,那是一個長到會塞滿螢幕的公式),或是懶得用工具解並判斷哪個是本題要的解之形式,你可以將方程式簡化成兩個式子:
X ^ 4 = H
和
(X + 3) ^ 4 = H
因此我們得到原方程式的解應介於
sqrt(sqrt(H)) - 3 ~ sqrt(sqrt(H))
之間。
各自代入看看哪個數字符合原方程式即是所求。
又或者是,我們可以從上面的兩條簡化的式子看到所求的 X 很接近 sqrt(sqrt(H)) 之值。而本題 H 的上界值為 2 ^ 64,也因此 X 的值上界為 2 ^ 16 = 65536。
因此,我們可以將 X = 1 ~ 65535 這些所有可能的 X 值求出其 X(X + 1)(X + 2)(X + 3) 之值(也就是每個 X 對應的 H 值)建成一個表格以供查詢。
接著對於每個輸入的 H 值,我們直接到剛剛建立的表格去找對應的 X 值即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。