นับจำนวนใน [1,N] ที่หาร X ลงตัวแต่ไม่หาร Y ลงตัวใน C++

ภาพรวมปัญหา

ให้จำนวน N, X, Y ต้องการนับจำนวนใน [1, N] ที่หาร X ลงตัว แต่ไม่หาร Y ลงตัว

ตัวอย่าง

Input: N=20, X=5, Y=20

Output: 2

คำอธิบาย: 5, 15 หาร 5 ลงตัว แต่ไม่หาร 20 ลงตัว

Input: N=20, X=4, Y=7

Output: 5

คำอธิบาย: 4, 8, 12, 16, 20 หาร 4 ลงตัว ไม่หาร 7 ลงตัว

แนวทางแก้ปัญหา (Naive)

1. วนลูป i = 1 ถึง N
2. ถ้า i % X == 0 && i % Y != 0 ให้เพิ่ม count

โค้ดตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

int divisibleXY(int x, int y, int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (i % x == 0 && i % y != 0) count++;
    }
    return count;
}

int main() {
    int N = 100, X = 6, Y = 8;
    cout << "Count: " << divisibleXY(X, Y, N);
    return 0;
}

ผลลัพธ์

Numbers from 1 to N which are divisible by X and not Y: 12

แนวทางคณิตศาสตร์ O(1)

จำนวนที่หาร X ลงตัวใน [1,N] = ⌊N/X⌋

จำนวนที่หาร X และ Y ลงตัว = ⌊N/LCM(X,Y)⌋

คำตอบ = ⌊N/X⌋ - ⌊N/LCM(X,Y)⌋

โค้ด O(1)

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

int divisibleXY_fast(int x, int y, int n) {
    long long lcm = 1LL * x / gcd(x, y) * y;
    return n / x - n / lcm;
}

int main() {
    int N = 100, X = 6, Y = 8;
    cout << "Count: " << divisibleXY_fast(X, Y, N);
    return 0;
}

ความซับซ้อน

หลักการ Inclusion-Exclusion

|A ∪ B| = |A| + |B| - |A ∩ B|

ที่นี่ต้องการ |A \ B| = |A| - |A ∩ B| โดย A = multiples of X, B = multiples of Y

A ∩ B = multiples of LCM(X,Y)