-
Notifications
You must be signed in to change notification settings - Fork 7
/
Program.cs
37 lines (34 loc) · 848 Bytes
/
Program.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using System;
namespace UglyNumberIII
{
class Program
{
static void Main(string[] args)
{
int n = 4, a = 6, b = 3, c = 4;
Console.WriteLine(NthUglyNumber(n, a, b, c));
}
public static int NthUglyNumber(int n, int a, int b, int c)
{
long lcmAB = LCM(a, b), lcmAC = LCM(a, c), lcmBC = LCM(b, c), lcmABC = LCM(lcmAB, c);
long li = 0, hi = int.MaxValue;
while (li <= hi)
{
long mid = li + (hi - li) / 2;
long count = mid / a + mid / b + mid / c - mid / lcmAB - mid / lcmAC - mid / lcmBC + mid / lcmABC;
if (count < n) li = mid + 1;
else hi = mid - 1;
}
return (int)li;
}
public static long GCD(long num1, long num2)
{
if (num2 == 0) return num1;
return GCD(num2, num1 % num2);
}
public static long LCM(long num1, long num2)
{
return num1 * num2 / GCD(num1, num2);
}
}
}