Posters on Multiples
National Olympiad — National round (2025 season)
Submission name: poster.cpp
Problem summary
Houses are numbered 1 through N. On three passes, put a poster on every multiple of A, then B, then C, skipping any house that already has a poster. Count the houses receiving posters.
Input
N A B C.
Output
The total number of posted houses.
Constraints
1 ≤ N,A,B,C ≤ 10^9.
Worked example
An independently prepared example for this explanation.
Input
10 2 3 5
Output
8
Solution analysis
- A house is posted exactly when its number is divisible by at least one of A,B,C. Add the counts N/A, N/B, N/C, then subtract the counts divisible by each pair’s least common multiple.
- A house divisible by all three was added three times and subtracted three times, so add the count divisible by their triple lcm once. Compute lcm by dividing by gcd before multiplying.
- For N=10 and A,B,C=2,3,5, the sum of individual counts is 5+3+2=10. Pair intersections have sizes 1,1,0 and the triple intersection is empty, giving eight. Cap an lcm above N at N+1, since such an intersection has no houses and the full triple lcm could overflow.
Why it works
For a house belonging to one, two or three divisibility sets, inclusion–exclusion gives total weight respectively 1, 2−1=1 or 3−3+1=1. Unposted houses receive weight zero. The lcm counts compute each intersection exactly.
Watch out. Use lcm rather than products when divisors share factors. The triple lcm can exceed 64-bit range unless capped before multiplication.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <numeric>
using namespace std;
long long cappedLcm(long long a, long long b, long long limit) {
a /= gcd(a, b);
// Values above N contribute zero; cap before multiplication can overflow.
if (a > limit / b) {
return limit + 1;
}
return a * b;
}
int main() {
long long n, a, b, c;
cin >> n >> a >> b >> c;
long long ab = cappedLcm(a, b, n);
long long ac = cappedLcm(a, c, n);
long long bc = cappedLcm(b, c, n);
long long abc = cappedLcm(ab, c, n);
cout << n / a + n / b + n / c - n / ab - n / ac - n / bc + n / abc << '\n';
}