Skills101
← All coding problems

Count Numbers Divisible by Any

mediumMath & Number Theory+20 XPTime limit 2s

A festival has n lamps numbered 1 to n. There are k switches; switch i turns on every lamp whose number is a multiple of aᵢ. How many lamps end up on (divisible by at least one of the aᵢ)?

n can be as large as 10¹⁸, so you cannot check the lamps one by one.

Input:

  • line 1: n k
  • line 2: k integers a₁ … aₖ

Output: the number of lamps from 1 to n divisible by at least one aᵢ.

Constraints: 1 ≤ n ≤ 10¹⁸, 1 ≤ k ≤ 15, 1 ≤ aᵢ ≤ 10⁹ (values may repeat).

Think about it: inclusion–exclusion. Add n / aᵢ for each single number, subtract n / lcm(aᵢ, aⱼ) for each pair, add back for each triple, and so on over all 2ᵏ − 1 non-empty subsets. If an LCM grows beyond n, that subset (and every bigger one containing it) adds 0 — stop early, which also prevents overflow.

Sample input 1

20 2
2 3

Sample output 1

13

Sample input 2

100 3
4 6 10

Sample output 2

36

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.