leet code 1201. Ugly Number III.
Write a program to find the n-th ugly number.
Ugly numbers are positive integers which are divisible by a or b or c.
Example 1:
Input: n = 3, a = 2, b = 3, c = 5 Output: 4 Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.
Example 2:
Input: n = 4, a = 2, b = 3, c = 4 Output: 6 Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 12... The 4th is 6.
Example 3:
Input: n = 5, a = 2, b = 11, c = 13 Output: 10 Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.
Example 4:
Input: n = 1000000000, a = 2, b = 217983653, c = 336916467 Output: 1999999984
参考：
[1] leetcode discuss: https://leetcode.com/problems/ugly-number-iii/discuss/387539/cpp-Binary-Search-with-picture-and-Binary-Search-Template
[2] 欧几里得算法求最大公约数：https://www.cnblogs.com/kirito-c/p/6910912.html （给出的gcd代码有错误）
题目为：求能被a或b或c整除的第n小的正整数。
翻译：求argmin_N F(N)，F(N)= 能被a或b或c整除的，小于N的，数的个数，F(N) == n
进一步，令f(a)=能被a整除的小于N的数的个数，类似的f(b)，f(c)。令g(a,b)为a,b的最小公倍数。
则题目变为：argmin_N F(N), F(N) = f(a) + f(b) + f(c) - f(g(a,b)) - f(g(a,c)) - f(g(b,c)) + f(g(a,b,c)), F(N) == n
盗一张图来解释：a = f(a)，b=f(b)等等.
此时涉及到两个问题：
1. 怎么求小于N的能被a整除的数的个数f(a)？
2. 怎么求a和b的最小公倍数g(a,b)?
答： 1. N/a，所有能被a整除的数可以表示为p * a，p为正整数。则所有小于N且能表示为p*a的数的个数就是f(a)的值，而p的值可以从1到N/a。所以答案为N/a
2. 最小公倍数计算方式为 a * b / a和b的最大公约数。 最大公约数可以由欧几里得算法，也就是辗转相除法解决。
大致理解为：如果有较大数a和较小数b，如果a%b==0，则b就是a和b的最大公约数。
如果a%b!=0，假设a = q * b + r，r为余数，且a = s * t，b = u * t，t为a和b的约数，则有r = (s - q * u) * t，表明t也是a和b的余数的约数。所以b和r的最大公约数就是a和b的最大公约数。这样递归，在某次余数为0的时候，除数就是最大公约数。
代码可以写为：
int gcd(int a, int b){
int r = 0;
while (b){
r = a % b;
a = b;
b = r;
}
return a;
}
在得到f和g的计算方式后，就可以寻找满足F(N) == n 的最小的N了。可以看出F(N)是一个单调函数，即如果有M>=N，则有F(M)>=F(N)。
这类似于在有序数组里寻找值为n的元素的索引。F(N)就是一个数组，N是它的索引。因此，可以使用二分搜索。
insomniacat 提供了二分搜索的基本框架：
while(lo < hi) {
int mid = lo + (hi - lo) / 2;
if(Special condition passed)(optional):
return mid;
if(condition passed)
hi = mid;
else
lo = mid + 1;
}
return lo;
最终代码：
class Solution {
public:
int nthUglyNumber(int n, int a, int b, int c) {
int lo = 1, hi = 2 * (int)1e9;
long A = a, B = b, C = c;
long AB = A * B / gcd(A, B);
long AC = A * C / gcd(A, C);
long BC = B * C / gcd(B, C);
long ABC = A * BC / gcd(A, BC);
while (lo < hi){
int mid = (hi - lo) / 2 + lo;
// compute F(N)
long FN = mid / A + mid / B + mid / C - mid / AB - mid / AC - mid / BC + mid / ABC;
if (FN < n)
lo = mid + 1;
else
hi = mid;
}
return lo;
}
int gcd(long a, long b){
int r;
while (b){
r = a % b;
a = b;
b = r;
}
return a;
}
};