นับจำนวนที่เป็นตัวคูณร่วมของสองจำนวนในช่วงใน C++

ภาพรวมปัญหา

ให้จำนวน A, B และช่วง [START, END] กระเบื้องที่ A ทาสีขาว B ทาสีดำ ถ้าทาทั้งสองสีจะกลายเป็นสีเทา ต้องการนับกระเบื้องสีเทา (ตัวคูณร่วมของ A และ B)

ตัวอย่าง

Input: START=10, END=20, A=3, B=6

Output: 2

คำอธิบาย: 12, 18 เป็นตัวคูณของ 3 และ 6

Input: START=1, END=100, A=10, B=11

Output: 0

ข้อสังเกตสำคัญ

จำนวนที่หาร A และ B ลงตัว ⟺ จำนวนที่หาร LCM(A, B) ลงตัว

LCM(A, B) = A × B / GCD(A, B)

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

1. วนลูป i จาก START ถึง END
2. ถ้า i % A == 0 && i % B == 0 ให้เพิ่ม count

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

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

int countGrey(int start, int end, int a, int b) {
    int count = 0;
    for (int i = start; i <= end; i++) {
        if (i % a == 0 && i % b == 0) count++;
    }
    return count;
}

int main() {
    int START = 10, END = 30, A = 4, B = 3;
    cout << "Common multiples: " << countGrey(START, END, A, B);
    return 0;
}

ผลลัพธ์

Common multiples of A and B (grey tiles): 2

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

ให้ L = LCM(A, B)

ตัวคูณของ L ใน [START, END] = ⌊END/L⌋ - ⌈START/L⌉ + 1

โค้ด O(1)

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

int countGrey_fast(int start, int end, int a, int b) {
    long long L = 1LL * a / gcd(a, b) * b;
    if (L > end) return 0;
    
    long long first = ((start + L - 1) / L) * L; // ceil(start/L) * L
    long long last = (end / L) * L;              // floor(end/L) * L
    
    if (first > last) return 0;
    return (last - first) / L + 1;
}

ความซับซ้อน

การประยุกต์ใช้

ปัญหานี้คือการนับตัวคูณร่วม (Common Multiples) ในช่วง ใช้หลักการ Inclusion-Exclusion ได้ด้วย: count(A) + count(B) - count(LCM) แต่ที่นี่ต้องการเฉพาะตัวคูณร่วม (Intersection) จึงใช้ LCM โดยตรง