COMB17 - Editorial

editorial
1

Problem Statement:

Given a positive integer N and three positive integers A, B, and C , the task is to count the number of positive integers smaller than or equal to N that are divisible by at least one of A, B, or C.

Approach:

To solve this problem, we can use the principle of Inclusion-Exclusion. We first count the multiples of each individual number A, B, and C less than or equal to N. Then, we subtract the multiples that are common between pairs of numbers and add back the multiples that are common to all three numbers.

Steps:

1. Count Multiples of Each Number:

We start by counting the multiples of each individual number A, B, and C that are less than or equal to N because these are the numbers that are divisible by at least one of the given numbers.

For example:

  • S_a represents the count of numbers that are divisible by A and are less than or equal to N.
  • S_b represents the count of numbers that are divisible by B and are less than or equal to N.
  • S_c represents the count of numbers that are divisible by C and are less than or equal to N.
2. Count Multiples of Pairs:

Next, we calculate the counts of multiples of pairs of numbers. This step is crucial to correct the double counting of numbers that are divisible by more than one of the given numbers.

For example:

  • S_{ab} represents the count of numbers that are divisible by both A and B and are less than or equal to N.
  • S_{bc} represents the count of numbers that are divisible by both B and C and are less than or equal to ( N ).
  • S_{ac} represents the count of numbers that are divisible by both A and C and are less than or equal to N.
3. Count Multiples of All Three Numbers:

In this step, we calculate the count of multiples of all three numbers, which are divisible by A, B, and C simultaneously. This count is subtracted in the next step to correct for the triple counting of numbers that are divisible by all three numbers.

For example:

  • S_{abc} represents the count of numbers that are divisible by A, B, and C and are less than or equal to N.
4. Apply Inclusion-Exclusion Principle:

The Inclusion-Exclusion principle is applied to find the total count of numbers that are divisible by at least one of the given numbers. This principle helps to correct the counts calculated in the previous steps to avoid overcounting or undercounting.

The formula used is:
S = S_a + S_b + S_c - S_{ab} - S_{bc} - S_{ac} + S_{abc}

  • We add the counts of multiples of individual numbers S_a, S_b, and S_c.
  • We subtract the counts of multiples of pairs of numbers S_{ab}, S_{bc}, and S_{ac}.
  • We add back the count of multiples of all three numbers S_{abc} to correct for the triple counting.

This approach ensures that each number is counted exactly once if it is divisible by at least one of the given numbers.

Time Complexity:

  • Calculating S_a, S_b, and S_c: O(1)
  • Calculating S_{ab}, S_{bc}, and S_{ac}: O(log(min(A, B, C)))
  • Calculating S_{abc}: O(log(min(A, B, C)))
  • Total time complexity : O(Tlog(min(A, B, C)))

Space Complexity:

  • Constant extra space is required for storing the input and output variables, therefore, the space complexity is O(1) for each test case.
1 Like