Ugly Number III ใน C++ : หา Ugly Number ลำดับที่ N

โจทย์: หา **Ugly Number ลำดับที่ n** (1-indexed)

ตัวอย่าง

n = 3, a = 2, b = 3, c = 5

Ugly Numbers: 2, 3, 4, 5, 6, 8, 9, 10, ...

ลำดับที่ 3 คือ 4

แนวทาง: Binary Search + Inclusion-Exclusion Principle

ไม่สามารถ Generate ทีละตัวได้ (n ใหญ่ถึง 1e9) -> ใช้ **Binary Search** หาคำตอบ

ฟังก์ชันนับ (Count Function) - ok(x): นับว่ามี Ugly Numbers ≤ x กี่ตัว

ใช้หลัก Inclusion-Exclusion:

count(x) = x/a + x/b + x/c
         - x/lcm(a,b) - x/lcm(b,c) - x/lcm(a,c)
         + x/lcm(a, lcm(b,c))

จากนั้น Binary Search หาค่า x น้อยที่สุดที่ทำให้ count(x) >= n

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

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

class Solution {
public:
    lli gcd(lli a, lli b) { return b == 0 ? a : gcd(b, a % b); }
    lli lcm(lli a, lli b) { return a / gcd(a, b) * b; } // ป้องกัน Overflow

    // นับจำนวน Ugly Numbers <= x
    lli ok(lli x, lli a, lli b, lli c) {
        return x/a + x/b + x/c
             - x/lcm(a,b) - x/lcm(b,c) - x/lcm(a,c)
             + x/lcm(a, lcm(b,c));
    }

    int nthUglyNumber(int n, int a, int b, int c) {
        int low = 1;
        int high = 2 * (int)1e9; // Upper bound ตาม Constraints

        while (low < high) {
            int mid = low + (high - low) / 2;
            if (ok(mid, a, b, c) >= n)
                high = mid;
            else
                low = mid + 1;
        }
        return high; // หรือ low ก็ได้
    }
};

Input / Output

Input:  3 2 3 5
Output: 4

จุดสำคัญ (Key Points)

• ใช้ long long (lli) ป้องกัน Overflow ตอนคูณ LCM
• lcm(a,b) = a / gcd(a,b) * b คำนวณหารก่อนคูณ
• Binary Search บนช่วงคำตอบ (Answer Space) ไม่ใช่ Index
• Upper Bound 2e9 เพียงพอต่อ Constraints ทั่วไป

เทคนิคนี้ใช้ได้กับโจทย์หา "ค่าที่น้อยที่สุดที่ทำให้ f(x) >= K" โดย f(x) คำนวณได้ O(1) ครับ