Divisible by at least one: inclusion–exclusion

Pick a whole number from 1 to N at random. How likely is it to be divisible by at least one of a few given numbers? N is far too large to check every number.

What to build

A program that counts with inclusion–exclusion.

Requirements

  • Print count C, the number of whole numbers from 1 to N divisible by at least one of the divisors, and probability P, C ÷ N as a reduced fraction.
  • It must work for N up to 10¹², so it cannot test each number.

Input

One line: N, then the divisors.

Output

Two lines.

Constraints

1 ≤ N ≤ 10¹²; 1 to 10 divisors, each from 2 to 1000.

Example

Input:

100 2 3

Output:

count 67
probability 67/100

Why it works

Adding the multiples of each divisor counts numbers with several divisors more than once; inclusion–exclusion over all groups of divisors, using their least common multiple, corrects every overlap exactly.

Examples

Example 1 · Input
100 2 3
Expected output
count 67
probability 67/100
Example 2 · Input
30 2 3 5
Expected output
count 22
probability 11/15

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

For every non-empty group of the divisors, count the multiples of their least common multiple: N // lcm.

Hint 2

Add the counts of groups with an odd number of divisors and subtract those with an even number.

Solution

Show one correct solution (try it yourself first)
from fractions import Fraction
from itertools import combinations
from math import lcm

nums = list(map(int, input().split()))
n, divisors = nums[0], nums[1:]
count = 0
for size in range(1, len(divisors) + 1):
    for group in combinations(divisors, size):
        multiples = n // lcm(*group)
        count += multiples if size % 2 == 1 else -multiples
print("count", count)
print("probability", Fraction(count, n))

Lesson: Rules: not, or, and →