CF 1044403 - Расклейка афиш

CF 1044403 - \u0420\u0430\u0441\u043a\u043b\u0435\u0439\u043a\u0430 \u0430\u0444\u0438\u0448

Rating: -
Tags: -
Solve time: 52s
Verified: yes

Solution

Problem Understanding

We are given a street with houses numbered from 1 to n. A character walks along the street twice, placing posters on houses according to divisibility rules. On the first pass, every house whose index is divisible by a is selected. On the second pass, every house divisible by b is considered, but a poster is only added if that house did not already receive one during the first pass.

The task is to compute how many distinct houses receive at least one poster after both passes.

This is equivalent to counting integers in the range [1, n] that are divisible by a or divisible by b, with duplicates counted only once.

The constraints allow n, a, b up to 10^9. This immediately rules out iterating over all houses, since a linear scan up to 10^9 is impossible under typical limits. The solution must rely on arithmetic counting rather than simulation.

A naive mistake is to simulate marking houses for both passes. For example, if n = 10, a = 2, b = 3, we would explicitly mark 2, 4, 6, 8, 10 and then 3, 6, 9. This works for small n but fails completely when n is large.

Another subtle issue is double counting. A house divisible by both a and b must not be counted twice. For example, if n = 12, a = 3, b = 4, house 12 is divisible by both. Any correct solution must subtract such overlaps.

Approaches

The brute-force approach is straightforward. We iterate through every house from 1 to n and check whether it is divisible by a or by b. If so, we increment the answer. This is correct because it directly mirrors the process described. However, its cost is O(n), which becomes infeasible when n reaches 10^9, since that would require billions of checks.

The key observation is that divisibility forms regular arithmetic patterns. The number of integers in [1, n] divisible by a is exactly floor(n / a). Similarly, the number divisible by b is floor(n / b). The overlap, i.e. numbers divisible by both a and b, are those divisible by lcm(a, b), so we subtract floor(n / lcm(a, b)) once to avoid double counting. This reduces the problem to constant time arithmetic.

The transformation works because the original process is just a union of two periodic sets. Instead of enumerating elements, we count them using period lengths.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n)	O(1)	Too slow
Inclusion-Exclusion	O(1)	O(1)	Accepted

Algorithm Walkthrough

We compute how many numbers in [1, n] are divisible by a, how many are divisible by b, and subtract those divisible by both.

1. Compute ca = n // a, which counts multiples of a in the range. This works because every a-th number contributes exactly one valid house.
2. Compute cb = n // b for the same reason, counting multiples of b.
3. Compute lcm(a, b) using gcd(a, b). The overlap occurs exactly at multiples of the least common multiple because those are the numbers divisible by both a and b simultaneously.
4. Compute cab = n // lcm(a, b). This counts exactly the houses that were included twice in the previous two counts.
5. The final answer is ca + cb - cab.

The subtraction is necessary because every overlapping house is counted once in ca and once in cb, but should contribute only one poster.

Why it works

Every integer in [1, n] belongs to exactly one of three disjoint categories: divisible by a only, divisible by b only, or divisible by both. The first two categories are counted separately, while the third is counted twice. Subtracting the size of the third category restores correct counting. No other overlaps exist because divisibility is fully characterized by multiples of the lcm.

Python Solution

import sys
input = sys.stdin.readline

from math import gcd

def lcm(x, y):
    return x // gcd(x, y) * y

n = int(input())
a = int(input())
b = int(input())

ca = n // a
cb = n // b
cab = n // lcm(a, b)

print(ca + cb - cab)

The solution relies on integer division properties: n // k counts how many multiples of k lie in [1, n]. The lcm computation uses gcd to avoid overflow issues and ensures correctness even when a and b are large.

A common implementation pitfall is computing lcm as a * b directly, which can overflow or become incorrect in intermediate arithmetic. Using a // gcd(a, b) * b avoids that.

Another subtlety is ensuring integer division is used consistently; floating point division would break correctness.

Worked Examples

Example 1

Input:

n = 10, a = 2, b = 3

We compute:

Step	Value
ca = 10 // 2	5
cb = 10 // 3	3
lcm(2, 3) = 6
cab = 10 // 6	1
answer	5 + 3 - 1 = 7

This matches the idea that we take all multiples of 2 and 3, but avoid double counting 6.

The trace shows that overlaps are handled exactly once through subtraction.

Example 2

Input:

n = 5, a = 10, b = 20

Step	Value
ca = 5 // 10	0
cb = 5 // 20	0
lcm(10, 20) = 20
cab = 5 // 20	0
answer	0

No house satisfies either divisibility condition, so the result is zero.

This confirms that the formula naturally handles cases where both divisibility sets are empty.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a few arithmetic operations and one gcd computation
Space	O(1)	Constant number of variables

The solution comfortably fits constraints up to 10^9 since it avoids iteration entirely. Even for maximal inputs, only integer arithmetic is performed.

Test Cases

import sys, io
from math import gcd

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from math import gcd

    n = int(sys.stdin.readline())
    a = int(sys.stdin.readline())
    b = int(sys.stdin.readline())

    def lcm(x, y):
        return x // gcd(x, y) * y

    ca = n // a
    cb = n // b
    cab = n // lcm(a, b)

    return str(ca + cb - cab)

# provided samples
assert run("10\n2\n3\n") == "7"
assert run("5\n10\n20\n") == "0"

# custom cases
assert run("1\n1\n1\n") == "1", "single house always covered once"
assert run("12\n3\n4\n") == "6", "check overlap at lcm"
assert run("100\n7\n5\n") == str(100//7 + 100//5 - 100//35), "random correctness"
assert run("30\n6\n10\n") == str(30//6 + 30//10 - 30//30), "lcm equals both overlap"

Test input	Expected output	What it validates
1,1,1	1	minimal case, full coverage
12,3,4	6	overlap handling via lcm
100,7,5	formula correctness	general correctness
30,6,10	30//30 edge overlap	lcm edge case

Edge Cases

One edge case occurs when a and b are equal. For example, n = 20, a = 4, b = 4. The correct result is simply floor(20 / 4), since both passes select the same houses. The formula handles this because lcm(a, b) equals a, so the subtraction removes duplicate counting exactly once.

Another case is when one divisor exceeds n. For n = 5, a = 10, b = 3, the first pass contributes zero, and the second behaves normally. The lcm is 30, so no overlap is subtracted. The algorithm correctly reduces to counting only valid multiples.

A final case is when both a and b exceed n. Then all floor divisions are zero, and the result is correctly zero without special handling.