Принцип включения-исключения
В данной главе мы рассмотрим принцип включения-исключения, его основные понятия и применение в комбинаторике и теории множеств.
Принцип включения-исключения — это комбинаторный метод, позволяющий находить размер объединения множеств через размеры самих множеств и их пересечения.
Для любых множеств :
Для и :
Почему вычитаем пересечение?
В сумме элементы учтены дважды.
Поэтому вычитаем их один раз, чтобы каждый элемент учитывался ровно один раз.
Сколько существует перестановок чисел от до , таких что:
Обозначим:
Первый элемент: или варианта
Оставшиеся элементов переставляем произвольно:
Аналогично:
Это количество плохих перестановок.
Общее количество перестановок:
Ответ:
Даны числа и .
Нужно найти количество чисел из , взаимно простых с .
Вместо подсчёта взаимно простых чисел найдём:
Сколько чисел НЕ взаимно просты с
Пусть простые делители :
Но если просто сложить — некоторые числа посчитаются несколько раз.
Поэтому используем принцип включения-исключения.
Перебираем все подмножества простых делителей:
int solve(int n, int r) {
vector<int> p;
// находим простые делители 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;
}