Re: [問題] 有一題我解不出來(哭)
※ 引述《joleen60626 (Mr.Banana)》之銘言：
> http://zerojudge.tw/ShowProblem?problemid=d122
> 我會算階乘
> 可是我的問題出在要怎麼算幾個0
> 我有想到用2和5去檢驗
> 可是程式碼寫不出來><
> 麻煩請高手指點~感恩
推
08/10 21:45,
08/10 21:45
推
08/10 21:49,
08/10 21:49
對不起，我以為是算總位數....
簡單來說要配出10，得要2和5相乘，
不過在階乘中2的個數必大於5的個數，所以我們可以忽略。
題目現在就轉成，n!有幾個5的質因數，
首先我們可以知道
1~n中
{
是5的倍數的有 n/5 個數
是25的倍數有 n/25 個數
...
是5^k的倍數有 n/(5^k)個數
}
全部合計就是n!中5的質因數個數了
上述的原理如果覺得有點抽象
舉個例子好了
25會在 5的倍數被算一次 25的倍數又被算一次 可是125的倍數並不會被算一次(當然)
所以我們應該記錄每5的倍數的最大次方數，可是
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
1 1 1 1 1 是5的倍數
1 是25的倍數
會發現總和剛好是25! 5的質因數個數。
大概是這樣啦，我不太會講那個概念。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.171.132.4
※ 編輯: yuscvscv 來自: 118.171.132.4 (08/10 22:08)
※ 編輯: yuscvscv 來自: 118.171.132.4 (08/10 22:45)
討論串 (同標題文章)