問題文:
n進数(8≦n≦36)のm(12桁以内)が与えられる。m!をn進数にすると、0がいくつ続くか。
解法:
10の階乗に0がいくつ続いてるかの考え方のアレをn進数に適用する。
まず、10進数で考えてみる。
(m!に0がいくつ続いているか) = min(m!に掛けられている2の数,m!に掛けられている5の数)
は少し考えればわかる。
そして、いくつ掛けられているかを取り出すには以下のようなステップをふむ。
たとえば、8!に、2がいくつ掛けられているかというのは
8! = 1 2 3 4 5 6 7 8 (掛け算記号省略)
で、2の倍数の因数が4個含まれていることがわかる。さらにこれを2^4で割ると、
8!/(2^4) = 1 1 3 2 5 3 7 4
となり、さらに、この中に含まれている2の倍数は2,4なので・・みたいなかんじで、終わりまでやってく。
結局 4 + 2 + 1 で 2は7回掛けられていることになる。
----
これらをn進数に適用してみると、nを素因数分解して、その因数が何個含まれているかみたいなノリでできる。
たとえば、12進数だったら、2*2*3なので、2*2のセットと3のセットの個数の最小みたいな見方をする。
説明ひどすぎ...
#include <iostream> #include <map> #include <climits> using namespace std; unsigned long long to(string w , int base){ unsigned long long ans = 0; for(int i = 0 ; i < w.size() ; i++) ans = ans * base + (w[i] >= 'A' ? w[i] - 'A' + 10 : w[i] - '0'); return ans; } map<int,int> factor(int n){ map<int,int> w; for(int i = 2 ; i*i<=n ; i++) while(n%i==0) w[i]++ , n /= i; if(n!=1) w[n]++; return w; } int main(){ int n; string m; while(cin >> n >> m && n){ unsigned long long v = to(m,n) , ans = -1; map<int,int> r = factor(n); for( map<int,int>::iterator it = r.begin() ; it != r.end() ; ++it){ int a = it->first; int d = it->second; unsigned long long t = v; unsigned long long ok = 0; while(t){ ok += (t / a) ; t /= a;} ans = min(ok / d , ans); } cout << ans << endl; } }
