Fill the Box
National Olympiad — National round (2011 season)
Submission name: cubes.cpp
Problem summary
Fill an N by M by K box exactly with equal cubes whose side is an integer number of centimetres. Minimize the number of cubes.
Input
Three positive integers N, M, K.
Output
The minimum number of cubes.
Constraints
1 ≤ N, M, K ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
40 50 30
Output
60
Solution analysis
- A cube side must divide every dimension, otherwise a row cannot fit exactly. The greatest possible side is gcd(N,M,K).
- For side g, the three directions contain N/g, M/g and K/g cubes. Multiply these counts using long long.
- For 40,50,30 the gcd is 10. There are 4 × 5 × 3 = 60 cubes.
Why it works
Every feasible integer side divides all dimensions and is at most their gcd. The gcd itself fits every dimension. Increasing the side decreases each directional count, so this feasible largest side minimizes the product.
Complexity: O(log(max(N,M,K))) time; O(1) extra space.
Watch out. The answer can approach 10^18. Divide each dimension before multiplying.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <numeric>
using namespace std;
int main() {
long long n, m, k;
cin >> n >> m >> k;
// The largest common integer side minimizes the cube count.
long long side = gcd(gcd(n, m), k);
cout << (n / side) * (m / side) * (k / side) << '\n';
}