Qo‘shish-ayirish prinsipi
Ushbu bobda biz qo‘shish-ayirish prinsipini, uning asosiy tushunchalari va kombinatorika hamda to‘plamlar nazariyasida qo‘llanilishini ko‘rib chiqamiz.
Qo‘shish-ayirish prinsipi — bu to‘plamlarning birlashmasi hajmini to‘plamlarning o‘z hajmlari va ularning kesishmalari hajmlari orqali topishga imkon beradigan kombinator usul.
Istalgan to‘plamlar uchun:
va uchun:
Nega kesishmani ayiramiz?
yig‘indisida elementlari ikki marta hisobga olingan.
Shuning uchun ularni bir marta ayiramiz, toki har bir element aynan bir marta hisobga olinsin.
dan gacha bo‘lgan sonlarning shunday permutatsiyalari nechta mavjudki:
Belgilaymiz:
Birinchi element: yoki variant
Qolgan elementni ixtiyoriy tartiblaymiz:
Xuddi shunday:
Bu yomon permutatsiyalar soni.
Permutatsiyalarning umumiy soni:
Javob:
va sonlari berilgan.
dan bilan o‘zaro tub bo‘lgan sonlar sonini topish kerak.
O‘zaro tub sonlarni sanash o‘rniga topamiz:
bilan o‘zaro tub EMAS bo‘lgan sonlar nechta
ning tub bo‘luvchilari:
Lekin shunchaki qo‘shib chiqilsa — ayrim sonlar bir necha marta hisoblanadi.
Shuning uchun qo‘shish-ayirish prinsipidan foydalanamiz.
Tub bo‘luvchilarning barcha qism to‘plamlarini ko‘rib chiqamiz:
int solve(int n, int r) {
vector<int> p;
// n ning tub bo‘luvchilarini topamiz
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;
}