yukicoder No.376 立方体のN等分 (2)
解法
最大のものについては明らかに N-1 が答えです。
最小のものが問題ですが, よくわからない方法で解いてしまった感があります。
まず N の約数を全列挙します。これをすべて格納した配列を div として, 後は約数の組 (div[i], div[j], div[k]) を全列挙すれば良いです。
ただ, これだと遅そうなので工夫をしていきます。まず, i, j を決めれば k については割り算で決定すれば良いだけなので, i, j だけ考えるようにしましょう。
で, i, j については, div[i] <= div[j] が成り立つようにします。こうすると, 必要な分割平面の数は, 少なくとも div[i]+div[j]-3 >= 2*div[i]-3 であると見積もれます。ans がある程度の値になっている場合, ans <= 2*div[i]-3 だったら枝刈りする, という高速化ができます。
また, div[i]*div[j] > N の場合は, j をそれより大きくする必要はないので, これで j についても枝刈りができます。
以上の枝刈りをすると, 十分高速に答えを求めることができました。
int main() { cin.tie(0); ios::sync_with_stdio(false); ll N; cin >> N; vector<ll> div; for (ll i = 2; i*i <= N; i++) { if (N%i == 0) { div.push_back(i); if (i*i != N) div.push_back(N/i); } } sort(div.begin(), div.end()); int sz = div.size(); ll ans = N-1; for (int i = 0; i < sz; i++) { if (ans+3 <= 2*div[i]) break; for (int j = i; j < sz; j++) { ll tmp = div[i]*div[j]; if (N < tmp) break; if (N%tmp) continue; tmp = N/tmp; ans = min(ans, div[i]+div[j]+tmp-3); } } cout << ans << " " << N-1 << endl; return 0; }