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