数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学丑陋数 III C++ 代码
假设我们要编写一个程序来查找第 n 个丑陋数。丑陋数是能被 a、b 或 c 整除的正整数。所以，例如，如果 n = 3，a = 2，b = 3 和 c = 5，那么输出将是 4，因为丑陋数是 [2,3,4,5,6,8,9,10]，第三个是 4。
要解决这个问题，我们将按照以下步骤进行 −
创建一个名为 ok() 的方法，它将获取 x、a、b 和 c，其作用如下 −
return (x/a) + (x/b) + (x/c) – (x/lcm(a,b)) - (x/lcm(b, c)) - (x/lcm(b,c)) - (x/lcm(a,c)) + (x/lcm(a, lcm(b,c)))
在 main 方法中，执行以下操作 −
low := 1，high := 2 * (10^9)
while low < high −
mid := low + (high - low) / 2
x := ok(mid, a, b, c)
如果 x >= n，那么 high := mid，否则 low := mid + 1
return high
示例 (C++)
让我们看看下面的实现，以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
typedef long long int 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 * b / gcd(a, b);
}
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;
while(low < high){
int mid = low + (high - low) / 2;
int x = ok(mid, a, b, c);
if(x>= n){
high = mid;
}
else low = mid + 1;
}
return high;
}
};
main(){
Solution ob;
cout << (ob.nthUglyNumber(3,2,3,5));
}输入
3 2 3 5
输出
4
更新日期：2020 年 4 月 29 日
192 次浏览
广告