When Supporters Meet Again
National Olympiad — National round (2019 season)
Submission name: supporter.cpp
Problem summary
All n supporters last met together on weekday s. Supporter i attends every di days. Determine the weekday of their next simultaneous meeting, with weekdays numbered 1 through 7.
Input
n and s, followed by n positive intervals di.
Output
The weekday number of the next meeting of everyone.
Constraints
1 ≤ n ≤ 100000; 1 ≤ s ≤ 7; 1 ≤ di ≤ 20.
Worked example
An independently prepared example for this explanation.
Input
3 1 2 5 10
Output
4
Solution analysis
- Everyone returns together after a positive number of days divisible by every attendance interval. The first such number is the least common multiple of all intervals.
- Build the LCM incrementally using lcm(a,b)=a/gcd(a,b)·b. Because every interval is at most 20, the final LCM divides lcm(1,…,20)=232792560, so a 64-bit integer is more than sufficient.
- Convert the weekday to zero-based form before shifting: (s−1+LCM)%7+1. In the second sample, the LCM of 1,2,3,4 is 12. Twelve days after weekday 2 is weekday 7.
Why it works
A simultaneous meeting offset must be a common multiple of every di, and every such common multiple is a valid offset. The LCM is the least positive one, so it gives the next meeting. Weekdays repeat every seven days, making the modular weekday formula exact.
Watch out. The next meeting is after the least positive common multiple, not after zero days. Subtract one before taking a modulo for weekdays numbered 1 through 7.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
int n, weekday;
cin >> n >> weekday;
long long period = 1;
for (int i = 0; i < n; ++i) {
long long interval;
cin >> interval;
// Divide before multiplying when extending the common meeting period.
period = period / gcd(period, interval) * interval;
}
cout << (weekday - 1 + period) % 7 + 1 << '\n';
}