Давхар тоологдсоныг ээлжлэн хасч, нэмж зөв тоог олдог Inclusion–Exclusion зарчим.

IntermediateХугацаа: O(2ᵏ · k)Санах ой: O(k)

Эхлээд жижиг бодлого

1-ээс 20 хүртэлх тооноос 2 эсвэл 3-т хуваагддаг нь хэд вэ? 2-т хуваагддаг 10, 3-т хуваагддаг 6.

6, 12, 18 гэсэн гурван тоо хоёуланд нь хуваагддаг тул хоёр удаа тоологджээ. Хариу 10 + 6 - 3 = 13.

Энгийн аргаас санаа руу

Энгийн арга: 1-ээс n хүртэлх тоо бүрийг шалгана. n = 10¹⁸ бол хэзээ ч дуусахгүй.

Гол санаа: d-д хуваагддаг тоо n хүртэл яг n / d бий. Анхны тоо бүрийнхийг нэмбэл давхар тоологдоно. Хоёр анхны тооны үржвэрийнхийг хасна. Гурвынхыг буцааж нэмнэ гэх мэт. Сондгой ширхэг анхны тоо сонгосон бол нэмж, тэгш бол хасна. k анхны тоонд 2ᵏ - 1 дэд олонлог бий.

Нэр томьёо ба тэмдэглэгээ

mask
Аль анхны тоог сонгосныг заах bitmask. mask >> i & 1 бол p[i] сонгогдсон.
prod
Сонгосон анхны тоонуудын үржвэр.
n / prod
1-ээс n хүртэл prod-д хуваагддаг тооны тоо.
bits
Сонгосон анхны тооны тоо. Сондгой бол нэмнэ, тэгш бол хасна.
1–10
1
·
2
·
3
·
4
·
5
·
6
·
7
·
8
·
9
·
10
·
11–20
11
·
12
·
13
·
14
·
15
·
16
·
17
·
18
·
19
·
20
·
21–30
21
·
22
·
23
·
24
·
25
·
26
·
27
·
28
·
29
·
30
·
ans = 0

1-ээс 30 хүртэлх тоонуудын хэд нь 2, 3, 5 гэсэн анхны тоонуудын ядаж нэгэнд хуваагдах вэ? Тоо бүрийн доор хэдэн удаа тоологдсоныг бичнэ. Төгсгөлд хуваагддаг тоо бүр яг ×1 байх ёстой.

Алхам 1 / 9
Хурд
  • Энэ алхамд нэмсэн
  • Энэ алхамд хассан
  • Тоологдсон
  • Хуваагддаг тоо
  • Хуваагдахгүй
Слайд 1 / 6

Давхар тоолохгүй

1-ээс 30 хүртэлх тооноос 2, 3, 5-ын аль нэгэнд хуваагддаг нь хэд вэ? 15 + 10 + 6 = 31 гэвэл 30-аас ч их гарна. Зарим тоог давхар тоолжээ.

inclusion-exclusion.cpp
#include <bits/stdc++.h>
using namespace std;
long long n, ans;
int k, p[20];
int main() {
cin >> n >> k;
for (int i = 0; i < k; i++) cin >> p[i];
for (int mask = 1; mask < (1 << k); mask++) {
long long prod = 1;
int bits = 0;
for (int i = 0; i < k; i++) {
if (mask >> i & 1) {
prod *= p[i];
bits++;
}
}
if (bits % 2 == 1) {
ans += n / prod;
} else {
ans -= n / prod;
}
}
cout << ans << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

1-ээс n хүртэлх тооноос өгсөн анхны тоонуудын аль нэгэнд хуваагддагийг n хэчнээн том байсан ч (10¹⁸ хүртэл) хурдан тоолох.

Яаж ажилладаг вэ?

1. Анхны тоонуудын хоосон биш дэд олонлог бүрийг bitmask ашиглан гүйлгэнэ. 2. Дэд олонлогийн үржвэрийг prod гэе. n хүртэл prod-д хуваагддаг тоо n / prod ширхэг бий. 3. Дэд олонлог сондгой ширхэг анхны тоотой бол нэмнэ, тэгш бол хасна. 4. Ингэхэд хуваагддаг тоо бүр яг нэг удаа тоологдоно. Оролт: эхний мөрөнд n ба k, дараагийн мөрөнд k ялгаатай анхны тоо. Гаралт: хуваагддаг тооны тоо.

Яагаад зөв, хэр хурдан бэ?

Яг j анхны тоонд хуваагддаг x тоог авъя. Тэр тоо 1 анхны тоотой дэд олонлогт j удаа, 2-той дэд олонлогт C(j, 2) удаа гарна гэх мэт. Нэмж, хассаны дүн нь C(j, 1) - C(j, 2) + C(j, 3) - … = 1. Тиймээс хуваагддаг тоо бүр яг нэг удаа тоологдоно, хуваагдахгүй тоо огт тоологдохгүй.

Дэд олонлог 2ᵏ - 1, тус бүрт k үйлдэл: O(2ᵏ · k). k = 15 бол 500 мянга орчим. n нь хэр том байх нь хамаагүй.

Түгээмэл алдаа

  • prod-ыг int-д хадгалах. Хэд хэдэн анхны тоо үржихэд хурдан томорно. long long хэрэглэ, бүр n-ээс хэтэрвэл тэр дэд олонлогийг алгас.
  • Тэмдгийг эсрэгээр нь авах: ганц анхны тоонд нэмэх ёстой.
  • Анхны биш тоо өгөгдвөл үржвэр нь хамгийн бага ерөнхий хуваагдагч биш болно. 4 ба 6-д хуваагддаг тоо 24 биш, 12-т хуваагддаг тоо.
  • mask = 0-ийг оруулах. Хоосон дэд олонлогийн хувьд n / 1 = n нэмэгдэж хариу буруу болно.

Хязгаарын тохиолдол

  • Ганц анхны тоо: хариу n / p. n = 10, p = 7 бол 1.
  • Анхны тоо n-ээс их: тэр анхны тоонд хуваагддаг тоо 0. Хариу зөв хэвээр.
  • n = 10¹⁸, p = 2, 3, 5: хариу 733333333333333334. long long хангалттай.

Өөрийгөө шалга

  1. 1-ээс 100 хүртэлх тооноос 2, 3, 5-ын аль нэгэнд хуваагддаг нь хэд вэ?

    Хариу харах

    50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.

  2. 4 анхны тоо өгөгдвөл хэдэн дэд олонлог шалгах вэ?

    Хариу харах

    2⁴ - 1 = 15.

  3. 2·3·5 = 30-д хуваагддаг тоог нэмэх үү, хасах уу?

    Хариу харах

    Нэмнэ. Гурван анхны тоо буюу сондгой ширхэг.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.1-ээс 30 хүртэлх тооноос 2, 3, 5-ын алинд нь ч хуваагддаггүй тоо хэд вэ?

    Hint харах

    Хуваагддаг нь 22. Нийт тооноос хас.

    Хариу ба тайлбар

    30 - 22 = 8: 1, 7, 11, 13, 17, 19, 23, 29.

  2. 2.Кодыг хуваагддаггүй тооны тоог хэвлэдэг болго.

    Hint харах

    ans-ийг өөрчлөхгүй, зөвхөн хэвлэх мөрийг засна.

    Хариу ба тайлбар

    cout << n - ans << '\n';. n = 60, p = 2, 3, 5, 7 бол хуваагддаг нь 46, хуваагддаггүй нь 14.

  3. 3.n хүртэлх тооноос m-тэй харилцан анхны тоо хэд байгааг ол. (Euler-ийн φ функц, m ≤ 10¹²)

    Hint харах

    Эхлээд m-ийг анхны үржвэрт задал. Харилцан анхны биш тоо нь эдгээр анхны тооны аль нэгэнд хуваагддаг.

    Хариу ба тайлбар

    m-ийн анхны хуваагчдыг олоод (12-оос олонгүй), Inclusion–Exclusion-оор хуваагддагийг тоолж, n-ээс хасна. n = m = 30 бол 30 - 22 = 8 = φ(30).

Жишээ

Оролт

30 3
2 3 5

Гаралт

22