「AOJ2081～2090」の編集履歴（バックアップ）一覧に戻る

AOJ2081～2090 - (2013/02/14 (木) 14:39:55) のソース

*2086　!
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2086
ｎ進数で表記された数ｍがある。
ｍ！をｎ進数で表したとき末尾にある0の数を答えよ。

解法
unsigned long long intでｍを数字になおして、後はｎ進数で表したとき末尾が0になるのはｍ！のなかにｎの素因数が何個あるか数えれば答えが出ます。


 #include<stdio.h>
 #include<string.h>
 #include<iostream>
 #include<map>
 void calcBase(int n,std::map<unsigned long long int,int>& base){
  	int ans=0;
	for(int i=2;i<=n;i++){
  		int p=0;
 		while(n%i==0){
 			n/=i;
 			p++;
 		}
 		if(p>0)base[i]=p;
 	}
 } 
  
 int main(){
 	int n;
 	char M[15];
 	std::map<unsigned long long int,int> base[37];
 	unsigned long long int num,p;
 	for(int i=8;i<=36;i++){
 		calcBase(i,base[i]);
 	}
 	while(1){
 		scanf("%d %s",&n,M);
 		if(n==0)break;
 		int len=strlen(M);
 		num=0;
 		p=1;
 		for(int i=len-1;i>=0;i--){
 			num+=(M[i]>='0'&&'9'>=M[i]?M[i]-'0':M[i]-'A'+10)*p;
 			p*=n;
  		}
 		
 		unsigned long long int t,b;
 		long long int ans=-1;
		for(std::map<unsigned long long int,int>::iterator it=base[n].begin();it!=base[n].end();it++){
  			t=0;
 			p=1;
 			b=(*it).first;
 			while(1){
 				p*=b;
 				t+=num/p;
 				if(num/p<b)break;
 			}
 			t/=(*it).second;
 			if(ans==-1||ans>t)ans=t;
 		}
 		std::cout<<ans<<"\n";
 	}
 }