นับจำนวนในช่วงที่หารทุกสมาชิกในอาร์เรย์ลงตัวใน C++

ภาพรวมปัญหา

ให้ช่วง [START, END] และอาร์เรย์ Arr[] ต้องการนับจำนวนในช่วงที่หารสมาชิกทุกตัวใน Arr[] ลงตัว

ตัวอย่าง

Input: START=1, END=20, Arr[]={2,4,8}

Output: 2

คำอธิบาย: 8, 16 หาร 2,4,8 ลงตัวทุกตัว

Input: START=100, END=200, Arr[]={230,321,490,521}

Output: 0

แนวทางที่ 1: Naive (ตรวจสอบทุกตัวหารทุกสมาชิก)

1. วนลูป i จาก START ถึง END
2. ตรวจสอบ i % arr[j] == 0 สำหรับทุก j
3. เวลา: O((END-START) × N)

โค้ด Naive

int divisiblebyArr_naive(int start, int end, int arr[], int len) {
    int count = 0;
    for (int i = start; i <= end; i++) {
        bool ok = true;
        for (int j = 0; j < len; j++) {
            if (i % arr[j] != 0) { ok = false; break; }
        }
        if (ok) count++;
    }
    return count;
}

แนวทางที่ 2: ใช้ LCM ของอาร์เรย์ (แนะนำ)

จำนวนที่หารทุกสมาชิกในอาร์เรย์ลงตัว ⟺ จำนวนที่หาร LCM ของอาร์เรย์ลงตัว

1. คำนวณ LCM ของสมาชิกทั้งหมดใน Arr[]
2. นับตัวคูณของ LCM ใน [START, END]

โค้ด LCM Approach

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int getLCM(int a, int b) {
    return 1LL * a / gcd(a, b) * b;
}

int getLCMArray(int arr[], int n) {
    int lcm = arr[0];
    for (int i = 1; i < n; i++) {
        lcm = getLCM(lcm, arr[i]);
        if (lcm > 1e9) break; // ป้องกัน overflow
    }
    return lcm;
}

int divisiblebyArr_lcm(int start, int end, int arr[], int len) {
    int lcm = getLCMArray(arr, len);
    if (lcm == 0 || lcm > end) return 0;
    
    long long first = ((start + lcm - 1) / lcm) * lcm;
    long long last = (end / lcm) * lcm;
    if (first > last) return 0;
    return (last - first) / lcm + 1;
}

ผลลัพธ์

Numbers that are divisible by all array elements: 2

ความซับซ้อน

ข้อควรระวัง

• LCM อาจ overflow — ใช้ long long และตรวจสอบ > END
• ถ้า LCM > END คำตอบคือ 0 ทันที
• Arr[] อาจมี 0 — ต้องกรองออกก่อน (หาร 0 ไม่ได้)