前往
大廳
主題

ZeroJudge - g470: 12869: Zeroes 解題心得

Not In My Back Yard | 2021-11-17 00:00:01 | 巴幣 0 | 人氣 386

題目連結:


題目大意:
定義一函數 fzero(x) 為 x!(即 x 階乘)末尾零之數量之值。例如 fzero(2) = 0(因為 2! = 2)、fzero(5) = 1(因為 5! = 120)、fzero(10) = 2(因為 10! = 3628800)等等。

輸入有若干列(最多有 50001 列輸入,最後將以一列「0 0」作結),每列給定兩正整數 low 、 high(0 < low ≦ high ≦ 9 × 10 ^ 18),試問 fzero(low) 、 fzero(low + 1) 、……、fzero(high) 有多少種不同的函數值?



範例輸入:
1 10
1 3
0 0


範例輸出:
3
1


解題思維:
以前的文章有解釋過 n! 之值是每 5 個數字會多至少一個零,因為一個 2 與一個 5 的乘積之值為 10,也就是會形成一個結尾的零。

而本題不需考慮 25 、 125 等等的倍數,因為本題只需要知道有多少種不同的函數值。因此,我們可以直接算 low ~ high 之間含有幾個 5 的倍數。可以看到該數量即為
floor(high ÷ 5) - floor(low ÷ 5) + 1
其中 floor() 代表為下高斯函數(即向下取整,對於「正數」來說形同無條件捨去)。而此值即為所求。




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

創作回應

第三方訪客
離散真的很重要
2022-04-22 00:10:33

更多創作