问题:
给定a,b,c
求出第n个能被a或b或c整除的正整数。(这种数也被称为:Ugly Number)
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, 10, 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 Constraints: 1 <= n, a, b, c <= 10^9 1 <= a * b * c <= 10^18 It's guaranteed that the result will be in range [1, 2 * 10^9]
解法:二分查找(Binary Search)
找到第一个正整数,使得其之前有n个,能被a或b或c整除的正整数。
求解对象范围:正整数:
- 最小:l:1
- 最大:r:INT_MAX
求解,m以内有多少个UglyNumber。
long getCount(long a, long b, long c, long m)
⚠️ 注意:
m以内有m/a个数能被a整除。
m以内有m/lcm(a,b)个数能被a且b整除。(lcm(a,b)为a和b的最小公倍数)
那么有,m以内有 m/a+m/b-m/lcm(a,b) 个数能被a或b整除。
能被a整除的 + 能被b整除的 - 能被a且b整除的(前面+算了两遍,这里需要减去一遍)
因此,对本问题则有:
要求的 能被a或b或c整除的 个数:
= 分别能被a,b,c整除的个数之和 - 分别能被a&&b,a&&c,b&&c整除的个数之和 + 能被a&&b&&c整除的个数之和
代码参考:
1 class Solution { 2 public: 3 long getCount(long a, long b, long c, long m) { 4 // 获取m以内,有多少个数,能被a或b或c整除(Ugly number) 5 long ab_count = m/lcm(a,b); 6 long ac_count = m/lcm(a,c); 7 long bc_count = m/lcm(b,c); 8 long abc_count = m/lcm(lcm(a,b),c); 9 return m/a + m/b + m/c - ab_count - ac_count - bc_count + abc_count; 10 } 11 int nthUglyNumber(int n, long a, long b, long c) { 12 long l = 1, r = INT_MAX; 13 while(l<r) { 14 long m = l+(r-l)/2; 15 if(getCount(a,b,c,m)>=n) { 16 r = m; 17 }else{ 18 l = m+1; 19 } 20 } 21 return l; 22 } 23 };