主題

ZeroJudge - f145: 肯尼的階乘位數 解題心得

Not In My Back Yard | 2021-01-30 00:00:01

題目連結:


題目大意:
已知 n!(n 階乘) = n × (n - 1) × (n - 2) × …… × 1 ,現定義 f(n) = n! × (n - 1)! × (n - 2)! × …… × 1! 、 g(n) = f(n) × f(n - 1) × f(n - 2) × …… × f(1)。

輸入第一列給定一正整數 t (1 ≦ t ≦ 100),代表有 t 筆測試資料,每筆佔一列。每列給定一正整數 n (1 ≦ n ≦ 10000),試問 g(n) 之值有幾位數?



範例輸入:
範例輸入 #1
6
1
2
3
4
5
6

範例輸入 #2
6
10
20
30
40
50
60

範例輸入 #3
6
100
200
300
400
500
600

範例輸入 #4
6
1000
2000
3000
4000
5000
6000


範例輸出:
範例輸出 #1
1
1
2
4
9
16

範例輸出 #2
92
977
3849
10125
21362
39224

範例輸出 #3
212953
2064381
7706081
19529518
40076101
71997781

範例輸出 #4
369262966
3348518328
12084996123
29967718292
60536387368
107441637210


解題思維:
對於某數 x ,其位數恰好為 floor( log(x) ) + 1 ,其中 floor 為下高斯函數(對於正數來說即是無條件捨去小數點)、log() 為以 10 為底的對數函數。已知對數有以下規則:
log( a × b ) = log( a ) + log( b ) 、
log( x ^ y ) = y × log( x )。

因此,我們可以看到 log( g(n) )
= log( f(n) × f(n - 1) × …… × f(1) )
= log( f(n) ) + log( f(n - 1) ) + …… + log( f(1) )
而 log( f(n) )
= log( n! × (n - 1)! × …… × 1! )
= log( n! ) + log( (n - 1)! ) + …… + log( 1! )
再加上 log( n! )
= log( n × (n - 1) × …… × 1 )
= log( n ) + log( n - 1 ) + …… + log( 1 )

所以我們定義 B[n] 、 F[n] 、 G[n] 分別為 n! 、 f(n) 、 g(n) 取對數之後的值,而根據上面的性質:
B[n] = B[n - 1] + log( n ) 、
F[n] = F[n - 1] + B[n] 、
G[n] = G[n - 1] + F[n]
而已知 log(1) = 0,所以 B[1] = F[1] = G[1] = 0。接著我們從 n = 2 開始建表建到 n = 10000。

然後所有輸入進來的 n 值,輸出 floor(G[n]) + 1 即是所求。但是要注意,該值可能會超過 32 位元有號整數(如 int)的儲存範圍,請改用 64 位元等等之型態(如 long long)。




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

創作回應

相關創作

更多創作