Leetcode-5198 Ugly Number III(丑数 III)

谁借莪１个温暖的怀抱￠ 2023-06-01 08:56 12阅读 0赞

1 #define _for(i,a,b) for(int i = (a);i < b;i ++)
     2 #define _rep(i,a,b) for(int i = (a);i > b;i --)
     3 #define INF 0x3f3f3f3f
     4 #define MOD 1000000007
     5 #define pb push_back
     6 #define maxn 100003
     7 typedef long long ll;
     8 class Solution
     9 {
    10     public:
    11         ll kk;
    12         ll aa;
    13         ll bb;
    14         ll cc;
    15         ll ab;
    16         ll bc;
    17         ll ca;
    18         ll abc;
    19         ll gcd(ll x,ll y)
    20         {
    21             return y?gcd(y,x%y):x;
    22         }
    23         ll lcm(long long a, long long b)
    24         {
    25             return a*b/gcd(a, b);
    26         }
    27         bool C(ll d)
    28         {
    29             return (d/aa+d/bb+d/cc-d/(ab)-d/(ca)-d/(bc)+d/(abc))>=kk;
    30         }
    31         ll solve()
    32         {
    33             ll lb = 0,ub = 2000000001;
    34             while(lb < ub)
    35             {
    36                 ll mid =  lb+(ub-lb)/2;
    37                 if(C(mid)) ub = mid;
    38                 else lb = mid+1;
    39             }
    40             return lb;
    41         }
    42         int nthUglyNumber(int n, int a, int b, int c)
    43         {
    44             kk = n;
    45             aa = a;
    46             bb = b;
    47             cc = c;
    48             ab = lcm(a,b);
    49             bc = lcm(b,c);
    50             ca = lcm(a,c);
    51             abc = lcm(ab,c);
    52             return solve();
    53         }
    54 };

转载于:https://www.cnblogs.com/Asurudo/p/11566946.html

发表评论取消回复

表情：

评论列表（有 0 条评论，12人围观）

还没有评论，来说两句吧...

相关阅读

相关 Ugly Numbers UVA 136 丑数

解题思路：首先丑数是指不能被2,3,5以外其他素数整除的数。最小的丑数数1，对任意一个丑数x；则2x,3x,5x也都是丑数，一个丑数有多种生成方式，所以，每取出一个丑数都

Bertha 。/ 2024年02月17日 18:47/ 0 赞/ 78 阅读

相关 Leetcode-5198 Ugly Number III(丑数 III)

1 define _for(i,a,b) for(int i = (a);i < b;i ++) 2 define _rep(i,a,b) for(int i

谁借莪１个温暖的怀抱￠/ 2023年06月01日 08:56/ 0 赞/ 13 阅读

相关【LeetCode】丑数（Ugly Number）☹☠☣☢☃

LeetCode丑数（Ugly Number）文章目录 LeetCode丑数（Ugly Number）丑数（搜狗百科）

秒速五厘米/ 2023年01月04日 10:30/ 0 赞/ 205 阅读

相关 leetcode 263, 264, 1201, 313. Ugly Number I, II, III, Super Ugly Number（leetcode 丑数问题合集）

263. Ugly Number [https://leetcode.com/problems/ugly-number/][https_leetcode.com_prob

逃离我推掉我的手/ 2022年10月10日 09:47/ 0 赞/ 35 阅读

相关 Leetcode: Single Number III

题目： Given an array of numbers `nums`, in which exactly two elements appear only once an

╰半橙微兮°/ 2022年08月09日 09:26/ 0 赞/ 24 阅读

相关 [leetcode]--260. Single Number III

Question 260: > Given an array of numbers nums, in which exactly two elements appear on

红太狼/ 2022年07月11日 22:56/ 0 赞/ 167 阅读

相关 leetcode 260. Single Number III

1.题目 Given an array of numbers nums, in which exactly two elements appear only once a

爱被打了一巴掌/ 2022年06月13日 01:24/ 0 赞/ 168 阅读

相关 leetcode 263. Ugly Number 丑数

Write a program to check whether a given number is an ugly number. Ugly numbers are pos

桃扇骨/ 2022年06月08日 13:24/ 0 赞/ 212 阅读

相关 leetcode 313. Super Ugly Number 超级丑数

Write a program to find the nth super ugly number. Super ugly numbers are positive numb

男娘i/ 2022年06月07日 01:06/ 0 赞/ 165 阅读

相关 [leetcode]Single Number III

趁热打铁，在[\[leetcode\]Single Number的来来往往][leetcode_Single Number]的基础上怒刷Single Number III。

末蓝、/ 2022年05月09日 09:50/ 0 赞/ 207 阅读