1
class Solution {
2
  public int nthUglyNumber(int n, int a, int b, int c) {
3
    int left = 1;
4
    int right = Integer.MAX_VALUE;
5
    int count = 0;
6
    while (left < right) {
7
      int middle = left + (right - left) / 2;
8
      if (isUgly(middle, a, b, c, n)) {
9
        right = middle;
10
      } else left = middle + 1;
11
    }
12
    return left;
13
  }
14

15
  public boolean isUgly(long middle, long a, long b, long c, long n) {
16
    return (int)
17
            (middle / a
18
                + middle / b
19
                + middle / c
20
                - middle / lcm(a, b)
21
                - middle / lcm(b, c)
22
                - middle / lcm(c, a)
23
                + middle / lcm(a, lcm(b, c)))
24
        >= n;
25
  }
26

27
  public long gcd(long a, long b) {
28
    if (a == 0) return b;
29
    else return gcd(b % a, a);
30
  }
31

32
  public long lcm(long a, long b) {
33
    return a * b / (gcd(a, b));
34
  }
35
}