網頁

2014年2月8日 星期六

UVa 10061 How many zero's and how many digits

題意:
  以B進位計算N!尾數有幾個0以及有幾個位數。

想法:
  1. 位數部分比較簡單,如果要知道n有幾位數,直接log(10,n)+1,那如果n要換成B進位的話就取log(B,n)+1,而log的計算規則,log(B,N!) = log(B,1)+log(B,2)+......+log(B,N)。
  2. 計算尾數有幾個0,對(N!)質因數分解,計算每個因數的數量,然後再看這些因數能夠湊成幾個B,例如B=20,那麼有2和5這兩個質因數能組成20,計算能夠湊成幾個,本題時間限制夠長,因此算因數的時候直接2~B枚舉即可。