1402. Inclusion-Exclusion via Bitmask

Given a positive integer N and a set of divisors, count how many integers in the range [1, N] are divisible by at least one of the divisors. Use the inclusion-exclusion principle over subsets of the divisors.

Input: A JSON object {"N": <upper bound>, "nums": [<divisors>]}.

Output: Return the count of integers in [1, N] divisible by at least one divisor.

Examples

Input: {"N":10,"nums":[2,3]}
Output: 7
Explanation: 5 + 3 - 1 = 7 integers up to 10.

Input: {"N":100,"nums":[3,5]}
Output: 47
Explanation: 33 + 20 - 6 = 47 integers up to 100.

Constraints

• 1 <= N <= 10^12
• 1 <= len(nums) <= 10
• 2 <= nums[i] <= 100

Asked by