SRM 507 Div1 500 CubePacking

問題
辺の長さが1の立方体がNs個、辺の長さがLの立方体がNb個ある。
これらの立方体を出来るだけ体積が小さい直方体に格納したい。
直方体の体積の最小値を求めよ。

解法
解の下限はNb*L*L*L+Nsである。
解の上限はNb*L*L*L+Ns+L*L-1である。（L*Lの底面を持つ直方体に立方体を詰め込む）
ということで、 解の候補をすべて列挙しても高々L*L程度のループをまわせばよい。

あとは、それぞれの解の候補に対して、その体積になるような直方体を全列挙すればよい。これは時間がかかりそうだが約数の個数は思ったほど多くないため十分に間に合う。

以下に整数の約数の個数がどの程度かを示す。
この結果はN周辺の数をサンプリングし、それらの約数の個数の平均値を取ったものである。

N	約数の個数
106	14.9
107	17.3
108	19.6
109	21.9

ざっくりと高々log(N)程度と覚えておくと良さそう（あくまでも平均値であることに注意）。

ソースコード

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

vector<long long> divisor(long long n) {
  vector<long long> ret;
  for (long long i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i != n / i)
        ret.push_back(n / i);
    }
  }
  return ret;
}

class CubePacking {
  public:
  int getMinimumVolume(int Ns, int Nb, int L) {
    int s = L*L*L*Nb+Ns;
    for (int x = s;; x++) {
      auto ds = divisor(x);
      REP (i, ds.size()) REP (j, i+1) {
        int a = ds[i];
        int b = ds[j];
        int c = x / a / b;
        if (a * b * c != x)
          continue;
        if ((a/L) * (b/L) * (c/L) >= Nb)
          return x;
      }
    }
    return -1;
  }
};