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:
kintegersa₁ … 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).