C ++中的丑陋数字III
假设我们必须编写一个程序来查找第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，其行为如下所示-
返回（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)）））
从主要方法中，执行以下操作-
低：=1，高：=2*（10^9）
而低<高-
中：=低+（高-低）/2
x：=ok(mid,a,b,c)
如果x>=n，则高：=中，否则低：=中+1
高回报
范例（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