Whole Wheel Revolutions
National Olympiad — National round (2016 season)
Submission name: rover.cpp
Problem summary
A rover has n axles. Wheels on the same axle have equal circumference; different axles may differ. Find the smallest positive travel distance that makes every wheel complete an integer number of revolutions.
Input
n followed by n positive integer wheel circumferences in metres.
Output
The smallest positive distance in metres.
Constraints
2 ≤ n ≤ 7; each circumference is 1–200 metres.
Worked example
An independently prepared example for this explanation.
Input
3 4 8 6
Output
24
Solution analysis
- A wheel completes a whole number of revolutions exactly when the distance is divisible by its circumference. The desired distance is therefore the least common multiple of all given circumferences.
- Combine one circumference at a time with current LCM L using L / gcd(L, x) × x. Divide before multiplying to reduce intermediate size. C++17 provides gcd in the numeric header.
- For 4, 8 and 6, the running LCMs are 4, then 8, then 24. Travelling 24 metres makes these wheels turn 6, 3 and 4 times respectively.
Why it works
The identity lcm(L, x) = Lx/gcd(L, x) gives the smallest positive common multiple of L and x. Starting with L = 1, induction shows the running value is the LCM of all processed circumferences. The final LCM is exactly the smallest distance divisible by every circumference.
Watch out. Use long long, since several relatively prime circumferences can create a large LCM. Divide by gcd before multiplying. The number of wheels per axle does not alter the LCM.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <numeric>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
long long distance = 1;
for (int i = 0; i < n; ++i) {
long long circumference;
cin >> circumference;
// Divide before multiplying when extending the least common multiple.
distance = distance / gcd(distance, circumference) * circumference;
}
cout << distance << '\n';
return 0;
}