The principle of inclusion-exclusion
In this chapter we will consider the inclusion-exclusion principle, its basic concepts and its application in combinatorics and set theory.
The inclusion-exclusion principle is a combinatorial method that allows one to find the size of the union of sets via the sizes of the sets themselves and their intersections.
For any sets :
For and :
Why do we subtract the intersection?
In the sum the elements of are counted twice.
Therefore we subtract them once so that each element is counted exactly once.
How many permutations of the numbers from to are there such that:
Let:
First element: or options
We permute the remaining elements arbitrarily:
Similarly:
This is the number of bad permutations.
Total number of permutations:
Answer:
The numbers and are given.
We need to find the number of numbers from that are coprime with .
Instead of counting coprime numbers, we will find:
How many numbers are NOT coprime with
Let the prime divisors of be:
But if we just add them up, some numbers will be counted multiple times.
Therefore we use the inclusion-exclusion principle.
We iterate over all subsets of prime divisors:
int solve(int n, int r) {
vector<int> p;
// find the prime divisors of n
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
p.push_back(i);
while (n % i == 0) {
n /= i;
}
}
}
if (n > 1) {
p.push_back(n);
}
int sum = 0;
for (int mask = 1; mask < (1 << p.size()); ++mask) {
int mult = 1;
int bits = 0;
for (int i = 0; i < (int)p.size(); ++i) {
if (mask & (1 << i)) {
mult *= p[i];
bits++;
}
}
int cur = r / mult;
if (bits % 2 == 1) {
sum += cur;
} else {
sum -= cur;
}
}
return r - sum;
}