主題

ZeroJudge - f649: 暐賢的體重 解題心得

Not In My Back Yard | 2021-02-15 00:00:06

題目連結:


題目大意:
輸入有多列,每列給定兩非負整數 N 、 M (0 ≦ N 、 M < 2 ^ 63),試問「N ^ M 的位數」之值有幾個位數(即 N ^ M 位數的位數)?



範例輸入:
5 3
9 53
95 3
953 953


範例輸出:
1
2
1
4


解題思維:
想當然耳,直接算出來 N ^ M 的值並不是一個實際的方式,所以我們可以試著從對數的角度出發(以下的對數全部以 10 為底數):

對數有一個性質
令 log(K) = a + b,則 a + 1 恰為 K 之位數
其中 a = floor(K) 為一整數(floor() 為下高斯函數,對於非負數字即無條件捨去小數部分)、 0 ≦ b < 1,且 a 稱為「指數」(Exponent)、b 稱為「尾數」(Mantissa)。

而且 log(N ^ M) = M × log(N),因此我們可以求得 N ^ M 之位數為
floor( M × log(N) ) + 1
我們令此值為 C1

而因為今天題目所求為 N ^ M 的位數之位數,所以我們再次套用相同的做法,得
floor( log(C1) ) + 1
令此值為 C2,而 C2 即是所求

……幾乎是啦。



值得注意的是 log(1) = 0 ,如果再取一次變為 log(0) 而對數並沒有定義 log(0) 之值,所以會炸掉。而一開始會出現 1 的情況為:N ≦ 1 或是 M = 0,兩者都會使得 N ^ M 之值為 1。

可以看到此時位數的位數為 1 ,所以這兩種可以預先判斷。剩下的即是按照上面的作法求出 C2 即是所求。




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

創作回應

相關創作

更多創作