AOJ : 2086 - !
問題概要
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2086
入力N,Mが与えられます.
Mは, N進数であらわされた12文字以下の文字列です.
このとき, M! (Mの階乗) の計算結果の下位何桁がゼロで埋まるかを答える問題です.
アルゴリズム
Factorial II (http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0052&lang=jp) の問題の発展です.
10進数の場合の計算方法は, 次のページのとおりで, これをN進数のパターンに発展させましょう.
http://www.tcp-ip.or.jp/~n01/math/factorial.pdf
プログラム
#include <iostream> #include <vector> #include <cstdlib> #include <climits> using namespace std; typedef unsigned long long ll; int main(void){ int N; string M; while(cin>>N>>M, N){ ll m = strtoll(&M[0],NULL,N); //10進数への変換 vector<int> v,s; //v:素因数列挙 s:各素因数の個数 //素因数分解 for(int i=2;i<=N;i++){ if(N % i != 0) continue; v.push_back(i); s.push_back(0); //iによって何回割り切れるか調べる while(N % i == 0){ s[v.size()-1]++; N /= i; } } ll ans = ULLONG_MAX; for(int i=0;i<v.size();i++){ ll tmp = m; ll zero = 0; while(tmp /= v[i]) zero += tmp; ans = min(ans,zero/s[i]); } cout<<ans<<endl; } return 0; }