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, andprobability 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
100 2 3
count 67 probability 67/100
30 2 3 5
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))