LeetCode 1201. 丑数 III(最小公倍数+二分查找)

1. 题目

请你帮忙设计一个程序,用来找出第 n 个丑数。

丑数是可以被 a b c 整除的 正整数。

示例 1:
输入:n = 3, a = 2, b = 3, c = 5
输出:4
解释:丑数序列为 2, 3, 4, 5, 6, 8, 9, 10... 其中第 3 个是 4。

示例 2:
输入:n = 4, a = 2, b = 3, c = 4
输出:6
解释:丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。

示例 3:
输入:n = 5, a = 2, b = 11, c = 13
输出:10
解释:丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。

示例 4:
输入:n = 1000000000, a = 2, b = 217983653, c = 336916467
输出:1999999984
 
提示:
1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
本题结果在 [1, 2 * 10^9] 的范围内

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/ugly-number-iii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

2. 解题

class Solution {
public:
    long nthUglyNumber(long n, long a, long b, long c) {
    	long long mid;
    	long long lcm_ab = lcm(a,b);//ab的最大公约数 
    	long long lcm_ac = lcm(a,c);// ac
    	long long lcm_bc = lcm(b,c);// bc
    	long long lcm_abc = lcm(a,lcm_bc);//abc的最大公约数 
        //一个周期内,abc的最大公约数假设为n,有多少个丑数?
        //是 a 的倍数的 n/a 个 减去重复的 case 4,6,7         case 1
        //是 b 的倍数的 n/b 个 减去重复的 case 4,5,7         case 2
        //是 c 的倍数的 n/c 个  减去重复的 case 5,6,7        case 3
        //是 ab 的倍数的 n/lcm_ab 个 减去重复的 case 7       case 4
        //是 bc 的倍数的 n/lcm_bc 个 减去重复的 case 7       case 5
        //是 ac 的倍数的 n/lcm_ac 个 减去重复的 case 7       case 6
        //是 abc 的倍数的 n/lcm_abc = 1 个                  case 7
        //case1-7汇总:如下
        long long count = lcm_abc/a + lcm_abc/b + lcm_abc/c - lcm_abc/lcm_ab - lcm_abc/lcm_ac - lcm_abc/lcm_bc + 1;
    	long long factor = n/count;//到lcm_abc处有count个丑数,n个丑数还需要几倍
    	long long rest = n%count;//剩余的个数
    	long long ans = factor*lcm_abc;//在factor*lcm_abc处已经得到,还差rest个丑数

    	if(rest > 0)
    	{
    		long long l = 1, r = lcm_abc, mid;
    		while(l <= r)
    		{
    			mid = l+((r-l)>>1);
    			count = mid/a + mid/b + mid/c - mid/lcm_ab - mid/lcm_ac - mid/lcm_bc + mid/lcm_abc;
    			if(count >= rest)
    				r = mid-1;
    			else// if(count < rest)
    				l = mid+1;
    		}
    		ans += l;
    	}
    	return ans;
    }

    long lcm(long a, long b)//最小公倍数
    {
    	return a*b/gcd(a,b);
    }
    long gcd(long a, long b)//最大公约数
    {
    	long r;
    	while(b)
    	{
    		r = a%b;
    		a = b;
    		b = r;
    	}
    	return a;
    }
};

二分处还可以写做:

while(l < r)
{
	mid = l+((r-l)>>1);
	count = mid/a + mid/b + mid/c - mid/lcm_ab - mid/lcm_ac - mid/lcm_bc + mid/lcm_abc;
	if(count >= rest)//mid处可能是答案,因为最后如[1,2]取不到2,不能mid-1
		r = mid;
	else// if(count < rest)
		l = mid+1;
}

0 ms 6 MB

上一篇:数论基础 gcd与lcm


下一篇:6572. lg