หาพจน์ที่ N ที่หารด้วย A หรือ B ลงตัวใน C++

ให้ A, B, N หาพจน์ที่ N ที่หารด้วย A หรือ B ลงตัว

ตัวอย่าง: A=4, B=3, N=5 → 9 (ลำดับ: 3,4,6,8,9,12...)

วิธีแก้ปัญหา 1: Brute Force

นับตัวเลขที่หารด้วย A หรือ B ลงตัวจนครบ N ตัว

วิธีแก้ปัญหา 2: Binary Search (มีประสิทธิภาพมากกว่า)

ใช้สูตรนับจำนวนที่หารลงตัว: count = mid/A + mid/B - mid/lcm(A,B)

Binary search หาค่า mid ที่ทำให้ count ≥ N

ตัวอย่างโค้ด C++ (Binary Search)

#include <iostream>
using namespace std;

int findLCM(int a, int b) {
    int lcm = a, i = 2;
    while (lcm % b != 0) { lcm = a * i; i++; }
    return lcm;
}

int findNTerm(int N, int A, int B) {
    int start = 1, end = N * A * B, mid;
    int LCM = findLCM(A, B);
    while (start < end) {
        mid = start + (end - start) / 2;
        if ((mid/A + mid/B - mid/LCM) < N) start = mid + 1;
        else end = mid;
    }
    return start;
}

int main() {
    int N = 12, A = 3, B = 4;
    cout << N << "th term divisible by " << A << " or " << B << " is " << findNTerm(N, A, B);
    return 0;
}

Output

12th term divisible by 3 or 4 is 24