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;
}