Bangladesh OI 2016 National Round pB. Beautiful Factorial Game ( Math )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf
Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces

題意：
給 N, K，求 N! 整除 K ^ x 的最大 x 是多少。

資料規模：
For easy version: 1 ≤ n ≤ 10, 2 ≤ k ≤ 10. [20% of total score]
For harder version: 1 ≤ n ≤ 100000000, 2 ≤ k ≤ 100000000. [100% of total score]
TL: 1000 ms
ML: 256 MB

解法：
令 F( t ) = N ! 整除 t ^ x 的最大 x。
我們想知道的其實是 [ 1, N ] 中的，對 K 質因數分解為 p1^n1 * p2^n2 .. 後，min{ F( p ) / n1, for all p }
因為 [ 1, N ] 中 A 的倍數有 N / A 個，因此當 p 為質數，F( p ) = Sigma{ N / p ^ r, for all positive integers r }

時間 / 空間複雜度：
O( 2^9 ) / O( 9 )

void solve(){
  int T; cin >> T;
  for( int kase = 1; kase <= T; ++kase ){
    cout << "Case " << kase << ": ";
    int N, K; cin >> N >> K;
    vp pf;
    int _k = K;
    for( int i = 2; i * i <= K; ++i ){
      int cnt = 0;
      while( _k % i == 0 ){
        _k /= i;
        ++cnt;
      }
      if( cnt > 0 ){
        pf.emplace_back( i, cnt );
      }
    }
    if( _k > 1 ){
      pf.emplace_back( _k, 1 );
    }
    ll ans = INF;
    for( int i = 0; i < pf.size(); ++i ){
      ll cnt = 0;
      for( ll v = pf[ i ].first; v <= 1LL * N; v *= pf[ i ].first ){
        cnt += N / v;
      }
      upmin( ans, cnt / pf[ i ].second );
    }
    cout << ans << endl;
  }
}