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枚舉即可。

	#include <cstdio>
	#include <cmath>
	using namespace std;
	int main()
	{
	int N,B;
	while (scanf("%d%d",&N,&B) != EOF){
	double digit = 0;
	int factor[801] = {0};
	double log10_B = log10(B);
	// N!
	for (int i = 2; i <= N; i++){
	//計算位數
	digit += (log10(i) / log10_B); // 換底公式log(B,i)
	//計算i的質因數
	for (int temp = i, j = 2; j <= B; j++){
	while (temp % j == 0){
	factor[j]++;
	temp /= j;
	}
	}
	}
	// 計算有幾個0
	int nOf0 = 0;
	while (1){
	int temp = B;
	// 將因數從2~B跑過 看能不能使temp==1
	for (int i = 2; i <= B; i++){
	while (factor[i] && temp % i == 0){
	factor[i]--;
	temp /= i;
	}
	}
	if (temp == 1) nOf0++;
	else break;
	}
	printf("%d %d\n",nOf0,(int)digit+1);
	}
	return 0;
	}

view raw [UVa] 10061 How many zero's and how many digits.cpp hosted with ❤ by GitHub