※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「AOJ2081~2090」の編集履歴(バックアップ)一覧に戻る

AOJ2081~2090 - (2013/02/14 (木) 14:39:55) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+*2086 !
+http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2086
+n進数で表記された数mがある。
+m!をn進数で表したとき末尾にある0の数を答えよ。
 
+解法
+unsigned long long intでmを数字になおして、後はn進数で表したとき末尾が0になるのはm!のなかにnの素因数が何個あるか数えれば答えが出ます。
+
+
+ #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";
+ 	}
+ }