切換
舊版
前往
大廳
主題

ZeroJudge - e473: 整數的位數 解題心得

Not In My Back Yard | 2019-10-17 23:10:01 | 巴幣 0 | 人氣 200

題目連結:


題目大意:
給定兩正整數 a 、 b (a ≦ 100, b ≦ 65535),求 a 的 b 次方有幾位數?



範例輸入:
2 8000


範例輸出:
2409


解題思維:
這題關係到的數學性質為「對數」(Logarithm),屬於高中數學的範疇。基本上這題就是數學題。

令 x 滿足 a ^ x = b,則 x = loga b 。此時,x 為 b 的對數(對於底數 a 而言)。而對數有一些基本性質,例如:
log a + log b = log (a × b) (注:底數為 10 時可忽略不寫)
log (a ^ b) = b × log a
b × log a = c + d ,其中 c 是一整數、0 ≦ d < 1。則 c + 1 即是 a ^ b 之位數長(前提是 a ^ b ≧ 1)

因此,我們可以利用上述最後一個性質求出所求——即 b × log a + 1 取整。log 通常在程式語言裡有內建函數可以使用,但是要注意其底數。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

胖胖貓
log a + log b = log (a + b) ... 這行寫錯囉
log a + log b = log (a x b)
2019-10-17 23:20:10
Not In My Back Yard
啊,不好意思XD
2019-10-17 23:39:30
Not In My Back Yard
感謝提醒
2019-10-17 23:39:55

更多創作