C++の醜い番号III

n番目の醜い数を見つけるプログラムを書かなければならないとしましょう。醜い数は、aまたはbまたはcで割り切れる正の整数です。したがって、たとえば、n=3およびa=2、b=3およびc=5の場合、醜い数は[2,3,4,5,6,8,9,10]であるため、出力は4になります。 、3番目は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）））

• メインの方法から、次のようにします-

• 低：=1、高：=2 *（10 ^ 9）

• 低<高-

  • 中：=低+（高-低）/ 2

  • x：=ok（mid、a、b、c）

  • x> =nの場合、high：=mid、それ以外の場合、low：=mid + 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