Принсипи дохилкунӣ-истисноӣ
Дар ин боб мо принсипи дохилкунӣ-истисноро, мафҳумҳои асосии он ва татбиқи онро дар комбинаторика ва назарияи маҷмӯаҳо баррасӣ мекунем.
Принсипи дохилкунӣ-истисно — ин усули комбинаторӣ мебошад, ки имкон медиҳад андозаи иттиҳоди маҷмӯаҳо тавассути андозаҳои худи маҷмӯаҳо ва буришҳои онҳо ёфта шавад.
Барои ҳар гуна маҷмӯаҳои :
Барои ва :
Чаро буришро тарҳ мекунем?
Дар суммаи унсурҳои ду маротиба ҳисоб шудаанд.
Аз ин рӯ, онҳоро як маротиба тарҳ мекунем, то ҳар як унсур маҳз як маротиба ҳисоб карда шавад.
Чанд ҷойивазкунии ададҳо аз то вуҷуд дорад, ки:
Нишон медиҳем:
Унсури аввал: ё вариант
унсури боқимондаро ихтиёрӣ ҷойиваз мекунем:
Ба ҳамин монанд:
Ин шумораи ҷойивазкуниҳои бад аст.
Шумораи умумии ҷойивазкуниҳо:
Ҷавоб:
Ададҳои ва дода шудаанд.
Лозим аст шумораи ададҳо аз , ки бо ба ҳам содаанд, ёфта шавад.
Ба ҷои ҳисоб кардани ададҳои ба ҳам сода меёбем:
Чанд адад бо ба ҳам сода НЕ ҳастанд
Бигзор тақсимкунандаҳои содаи :
Аммо агар танҳо ҷамъ кунем — баъзе ададҳо чанд маротиба ҳисоб мешаванд.
Аз ин рӯ принсипи дохилкунӣ-истисноро истифода мебарем.
Ҳамаи зермаҷмӯаҳои тақсимкунандаҳои содаро мегузаронем:
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;
}