1201.丑数III

链接：1201.丑数III
难度：Medium
标签：数学、二分查找、组合数学、数论
简介：给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。

题解 1 - cpp

• 编辑时间：2022-01-07
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：二分答案，求出在数值 x 之前有几个丑数。

class Solution {
   public:
    long long gcd(long long a, long long b) {
        if (b) return gcd(b, a % b);
        return a;
    }
    long long lcm(long long a, long long b) {
        return (long long)(a * b / gcd(a, b));
    }
    long long a, b, c, ab, ac, bc, abc;
    long long get(long long cnt) {
        //printf("a = %d, b = %d, c = %d, ab = %d, ac = %d, bc = %d, abc = %d
",
        //       a, b, c, ab, ac, bc, abc);
        return cnt / a + cnt / b + cnt / c - cnt / ab - cnt / bc - cnt / ac +
               cnt / abc;
    }
    int nthUglyNumber(int n, int a, int b, int c) {
        this->a = a;
        this->b = b;
        this->c = c;
        ab = lcm(a, b);
        ac = lcm(a, c);
        bc = lcm(b, c);
        abc = lcm(a, lcm(b, c));
        long long l = 1, r = 2000000000, m;
        while (l < r) {
            m = (l + r) / 2;
            if (get(m) >= n)
                r = m;
            else
                l = m + 1;
        }
        return l;
    }
};