Meeting at the Fountain
National Olympiad — National round (2026 season)
Submission name: fountain.cpp
Problem summary
Two walkers leave their homes at the same time. Reaching the fountain takes M and P minutes respectively. Each repeatedly walks home and back without waiting. Find the first time both are at the fountain, or −1 if that never happens.
Input
M on the first line and P on the second; any separating whitespace is accepted.
Output
The first meeting time in minutes, or −1.
Constraints
1 ≤ M, P ≤ 1,000,000,000.
Worked example
An independently prepared example for this explanation.
Input
6 10
Output
30
Solution analysis
- The first walker visits the fountain at M, 3M, 5M, … minutes; the second visits at P, 3P, 5P, … . Even multiples correspond to being back home.
- Let g = gcd(M,P), u = M/g and v = P/g. The smallest common multiple is L = (M/g)·P. Its arrival numbers are L/M = v and L/P = u.
- If both u and v are odd, L is a simultaneous fountain visit and is the earliest possible common visit. Otherwise one is even. Every common time is a multiple of L and that walker’s arrival number remains even, so no meeting is possible.
- For M = 6 and P = 10, g = 2, u = 3, v = 5: both are odd, so they meet at L = 30. For 5 and 10, the reduced values 1 and 2 fail the test.
Why it works
Any simultaneous visit must be a common multiple of M and P and must use odd multipliers for both. Since u and v are coprime, all common multiples are multiples of L. Odd u,v make L itself valid; if one is even, no multiple can make that quotient odd.
Watch out. The ordinary LCM alone is not enough: check that both quotients are odd. A meeting elsewhere on the walking routes does not count. Compute using long long and divide before multiplying; the answer can approach 10^18.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<numeric>
using namespace std;
int main() {
long long firstTime, secondTime;
cin >> firstTime >> secondTime;
long long commonDivisor = gcd(firstTime, secondTime);
long long reducedFirst = firstTime / commonDivisor;
long long reducedSecond = secondTime / commonDivisor;
if (reducedFirst % 2 == 0 || reducedSecond % 2 == 0) {
cout << "-1\n";
return 0;
}
// Divide first, keeping the common-multiple calculation in range.
cout << reducedFirst * secondTime << '\n';
}