【C++二分查找容斥原理】1201. 丑数 III

本文涉及的基础知识点

C++二分查找
容斥原理：组合数学汇总

LeetCode1201. 丑数 III

丑数是可以被 a 或 b 或 c 整除的正整数。
给你四个整数：n 、a 、b 、c ，请你设计一个算法来找出第 n 个丑数。
示例 1：
输入：n = 3, a = 2, b = 3, c = 5
输出：4
解释：丑数序列为 2, 3, 4, 5, 6, 8, 9, 10… 其中第 3 个是 4。
示例 2：
输入：n = 4, a = 2, b = 3, c = 4
输出：6
解释：丑数序列为 2, 3, 4, 6, 8, 9, 10, 12… 其中第 4 个是 6。
示例 3：
输入：n = 5, a = 2, b = 11, c = 13
输出：10
解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13… 其中第 5 个是 10。

提示：
1 <= n, a, b, c <= 10⁹
1 <= a * b * c <= 10¹⁸
本题结果在 [1, 2 * 10⁹] 的范围内

二分查找+容斥原理

Cnt(x)记录 [1,x]中被a或被b或被c整除的正数数量。
其结果为：被a整除+1 被b整除+1 被c整除+1
被lcm(a,b)整除-1，被lcm(a,c)整除-1 被lcm(b,c)整除-1
被 lcm(a,b,c)整除+1
[1,x]被a整除的数量为：x/a
二分查找类型：寻找首端
Check函数的范围：[1,2e9]
Check函数：return Cnt(mid) >= n
注意：lcm(a,b)可能超过整形范围，所以要lcm((long long)a,b) Cnt的返回值，也可能超过整形范围。

代码

核心代码

template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:int nthUglyNumber(int n, int a, int b, int c) {auto Cnt = [&](long long x) {return x / a + x / b + x / c - x / lcm((long long)a, (long long)b) - x / lcm((long long)b, c) - x / lcm((long long)a, c) + x / lcm(a, lcm((long long)b, c));};auto Check = [&](int mid) {return Cnt(mid) >= n;};return CBinarySearch<int>(1, 2e9 + 1).FindFrist(Check);}};

单元测试用例

int n,  a,  b,  c;TEST_METHOD(TestMethod11){n = 3, a = 2, b = 3, c = 5;auto res = Solution().nthUglyNumber(n, a, b, c);AssertEx(4, res);}TEST_METHOD(TestMethod12){n = 4, a = 2, b = 3, c = 4;auto res = Solution().nthUglyNumber(n, a, b, c);AssertEx(6, res);}TEST_METHOD(TestMethod13){n = 5, a = 2, b = 11, c = 13;auto res = Solution().nthUglyNumber(n, a, b, c);AssertEx(10, res);}TEST_METHOD(TestMethod14){n = 1000000000, a = 2, b = 217983653, c = 336916467;auto res = Solution().nthUglyNumber(n, a, b, c);AssertEx(1999999984, res);}TEST_METHOD(TestMethod15){n = 1, a = 1, b = 1, c = 1;auto res = Solution().nthUglyNumber(n, a, b, c);AssertEx(1, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功