ภาพรวมปัญหา
ได้รับ N นับจำนวนเต็มจาก 1 ถึง N ที่หาร 2 หรือ 3 หรือ 5 ลงตัว
ตัวอย่าง
อินพุต
N = 7
เอาต์พุต
5
คำอธิบาย
1-7: 2,3,4,5,6 หาร 2/3/5 ลงตัว (5 ตัว)
วิธีแก้ปัญหา
วิธีที่ 1: Brute Force - O(N)
วน 1 ถึง N เช็ค mod 2,3,5
วิธีที่ 2: Inclusion-Exclusion Principle - O(1) ⭐
ใช้หลักการรวม-ตัดออก (Inclusion-Exclusion):
|A∪B∪C| = |A|+|B|+|C| - |A∩B|-|A∩C|-|B∩C| + |A∩B∩C|
โดย |A| = N/2, |B| = N/3, |C| = N/5
|A∩B| = N/6, |A∩C| = N/10, |B∩C| = N/15
|A∩B∩C| = N/30
โค้ดตัวอย่าง (Bitmask)
#include <bits/stdc++.h>
using namespace std;
int countMultiples(int n) {
int values[] = {2, 3, 5};
int countMultiples = 0;
int bitMask = 1 << 3; // 2^3 = 8 subsets
for (int i = 1; i < bitMask; i++) {
int prod = 1;
for (int j = 0; j < 3; j++)
if (i & (1 << j))
prod *= values[j];
if (__builtin_popcount(i) % 2 == 1)
countMultiples += n / prod;
else
countMultiples -= n / prod;
}
return countMultiples;
}
int main() {
int n = 13;
cout << "The number of multiples till " << n << " is " << countMultiples(n);
return 0;
}
เอาต์พุต
The number of multiples till 13 is 9
สรุป
Inclusion-Exclusion ด้วย Bitmask ทุก subset ของ {2,3,5} Complexity O(2^k) = O(1) สำหรับ k=3
