Friends Meet Again
National Olympiad — National round (2012 season)
Submission name: friends.cpp
Problem summary
N friends are available every 1,2,…,N weeks respectively, starting from a Saturday when all meet. Find the first positive number of weeks until they can all meet again.
Input
The number N of friends.
Output
The smallest positive common meeting interval in weeks.
Constraints
1 < N ≤ 20.
Worked example
An independently prepared example for this explanation.
Input
3
Output
6
Solution analysis
- A future meeting week must be divisible by every availability period from 1 to N. This is their least common multiple.
- Start with answer=1 and merge each period i using answer/gcd(answer,i)*i. Dividing before multiplying avoids an unnecessarily large intermediate value.
- For N=3, the periods are 1,2,3. Their first common positive multiple is 6.
Why it works
After merging periods 1 through i, answer is their least common multiple, by the standard gcd–lcm identity. At i=N it is therefore the earliest week satisfying every friend’s schedule.
Complexity: O(N log A) time for gcd computations, with A the largest accumulated lcm; O(1) extra space.
Watch out. Print the interval, not a calendar date. A 64-bit integer comfortably holds lcm(1,…,20).
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <numeric>
using namespace std;
int main() {
int n;
cin >> n;
long long answer = 1;
for (int period = 1; period <= n; period++) {
// Merge one period into the lcm; divide before multiplying.
answer = answer / gcd(answer, static_cast<long long>(period)) * period;
}
cout << answer << '\n';
}