Формула включения-исключения: как посчитать числа до N, не делящиеся ни на одно из заданных простых?
Классическая задача: сколько чисел от 1 до N не делятся ни на 2, ни на 3, ни на 5, ни на 7? Понимаю, что нельзя просто вычесть N/2 + N/3 + ..., потому что что-то посчитается дважды. Как тут аккуратно применить формулу включения-исключения и как это кодить для произвольного набора простых?
2 ответа
Формула включения-исключения (ВИ): |A_1 ∪ ... ∪ A_m| = Σ|A_i| − Σ|A_i ∩ A_j| + Σ|A_i ∩ A_j ∩ A_k| − ... Знак чередуется по размеру подмножества. Здесь A_i — числа, делящиеся на p_i; |A_i| = N / p_i (целочисленно), а пересечение по подмножеству S — это N / (произведение p в S), потому что простые взаимно просты.
Количество чисел, делящихся хотя бы на одно — это объединение; «не делящихся ни на одно» = N − |объединение|. Перебираем все 2^m подмножеств битовой маской:
long long countCoprime(long long N, vector<long long>& p) {
int m = p.size();
long long divisible = 0;
for (int mask = 1; mask < (1 << m); mask++) {
long long prod = 1; int bits = 0;
bool overflow = false;
for (int i = 0; i < m; i++)
if (mask & (1 << i)) {
bits++;
if (prod > N / p[i]) { overflow = true; break; } // prod*p[i] > N
prod *= p[i];
}
if (overflow) continue; // вклад = N/prod = 0
long long term = N / prod;
divisible += (bits & 1) ? term : -term;
}
return N - divisible;
}
Сложность O(2^m · m). Подходит, пока простых немного (m ≤ ~20). Контроль переполнения произведения обязателен — иначе при больших p_i и long long словишь UB.
Альтернатива через знак на лету: можно сразу считать «не делящихся» как Σ_{S} (−1)^{|S|} · N/(∏ p_S), включая пустое подмножество (даёт +N). Тогда ответ = эта сумма напрямую, без отдельного вычитания. Это та же ВИ, просто переписанная — иногда чище в коде. И помни: works ровно потому, что p_i попарно взаимно просты; для произвольных (не взаимно простых) делителей в пересечении нужно брать НОК, а не произведение.