SRM335 D1E-D2M Multifactorial

TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$fac_k(n)$は次のように定義される．

$$ \begin{eqnarray} fac_k (n) &=& n\ \ \ if\ k >= n\\ fac_k (n) &=& n * fac_k(n - k)\ \ \ if\ k < n \end{eqnarray} $$

$n, k$が与えられるので，$fac_k(n)$を文字列で返す．$10 ^{18}$をより大きくなる場合は$overflow$を返す．

$n * fac_k(n - k)$が$10 ^{18}$より大きくなるかを判断したいが，そのままかけて比較すると実際に大きくなるときはオーバーフローしてしまうので，$10 ^ {18} >= i * ret$を$\frac{10 ^{18}}{i} >= ret$に変形する．

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

class Multifactorial {
  public:
  string calcMultiFact(int n, int k) {
      bool flag = true;
      ll ret = 1;
      for(int i = n; i > 0; i -= k) {
          if(1e18 / i >= ret) {
              ret *= i;
          } else {
              flag = false;
              break;
          }
      }

      if(flag) {
          string ans;
          stringstream ss;
          ss << ret;
          return ss.str();
      } else {
          return "overflow";
      }
  }
};