Equal Numbers of Bottles
National Olympiad — Regional round (2011 season)
Submission name: bottles.cpp
Problem summary
A quantity of water can fill only M-liter bottles or only N-liter bottles exactly. It is instead poured into equal positive numbers of both bottle types, again filling them exactly. Find the smallest possible total number of bottles used.
Input
Two integers M and N.
Output
The minimum total number of bottles in the mixed filling.
Constraints
0 < M, N < 50.
Worked example
An independently prepared example for this explanation.
Input
15 10
Output
12
Solution analysis
- If x bottles of each type are used, the water volume is x(M + N). It must be divisible by both M and N, because either single-type filling was possible.
- Let L = lcm(M, N). The condition is L divides x(M + N). The smallest positive x is L/gcd(L, M + N), so the answer is twice that value.
- For M = 15 and N = 10, L = 30 and M + N = 25. The smallest x is 30/gcd(30,25) = 6. Six bottles of each type hold 150 liters, and the total is 12 bottles.
Why it works
A volume admits both single-type fillings exactly when it is a multiple of L. Write g = gcd(L, M + N). Dividing L | x(M + N) by g leaves coprime factors L/g and (M + N)/g, so L/g must divide x. Its smallest positive value is therefore L/g, and twice this is the minimum total.
Watch out. Minimize a volume satisfying all three fillings, not simply lcm(M,N). The total bottle count is 2x, since each type is used x times.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <numeric>
using namespace std;
int main() {
long long m, n;
cin >> m >> n;
long long commonVolume = m / gcd(m, n) * n;
// Find the smallest x for which lcm(m, n) divides x * (m + n).
long long eachType = commonVolume / gcd(commonVolume, m + n);
cout << 2 * eachType << '\n';
}