題目連結:
題目大意:
定義一函數 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() 代表為下高斯函數(即向下取整,對於「正數」來說形同無條件捨去)。而此值即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。