{"id":3359,"date":"2018-07-28T22:15:21","date_gmt":"2018-07-29T05:15:21","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=3359"},"modified":"2018-07-28T22:26:43","modified_gmt":"2018-07-29T05:26:43","slug":"leetcode-878-nth-magical-number","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/math\/leetcode-878-nth-magical-number\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 878. Nth Magical Number"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

A positive integer\u00a0is\u00a0magical<\/em>\u00a0if it is divisible by either\u00a0A<\/span>\u00a0or\u00a0B<\/span>.<\/p>\n

Return the\u00a0N<\/span>-th magical number.\u00a0 Since the answer may be very large,\u00a0return it modulo\u00a0<\/strong>10^9 + 7<\/code>.<\/p>\n

\n

Example 1:<\/strong><\/p>\n

Input: <\/strong>N = 1<\/span>, A = 2<\/span>, B = 3<\/span>\r\nOutput: <\/strong>2<\/span>\r\n<\/pre>\n
\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>N = 4<\/span>, A = 2<\/span>, B = 3<\/span>\r\nOutput: <\/strong>6<\/span>\r\n<\/pre>\n
\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>N = 5<\/span>, A = 2<\/span>, B = 4<\/span>\r\nOutput: <\/strong>10<\/span>\r\n<\/pre>\n
\n
Example 4:<\/strong><\/p>\n
Input: <\/strong>N = 3<\/span>, A = 6<\/span>, B = 4<\/span>\r\nOutput: <\/strong>8<\/span>\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= N\u00a0<= 10^9<\/code><\/li>\n
  2. 2 <= A\u00a0<= 40000<\/code><\/li>\n
  3. 2 <= B\u00a0<= 40000<\/code><\/li>\n<\/ol>\n
    Solution: Math + Binary Search<\/strong><\/h1>\n
    Let n denote the number of numbers <= X that are divisible by either\u00a0A<\/span>\u00a0or\u00a0B.<\/span><\/p>\n
    n = X \/ A + X \/ B – X \/ lcm(A, B) = X \/ A + X \/ B – X \/ (A * B \/ gcd(A, B))<\/p>\n
    Binary search for the smallest X such that n >= N<\/p>\n
    Time complexity: O(log(1e9*4e5)<\/p>\n
    Space complexity: O(1)<\/p>\n
    \/\/ Author: Huahua\r\n\/\/ Running time: 0 ms\r\nclass Solution {\r\npublic:\r\n  int nthMagicalNumber(int N, int A, int B) {\r\n    const int kMod = 1000000007;\r\n    long l = 2;\r\n    long r = static_cast<long>(1e9 * 4e5);\r\n    int d = gcd(A, B);\r\n    while (l < r) {\r\n      long m = (r - l) \/ 2 + l;\r\n      if (m \/ A + m \/ B - m \/ (A * B \/ d) < N)\r\n        l = m + 1;\r\n      else\r\n        r = m;\r\n    }\r\n    return l % kMod;\r\n  }\r\nprivate:\r\n  int gcd(int a, int b) {\r\n    if (a % b == 0) return b;\r\n    return gcd(b, a % b);\r\n  }\r\n};<\/pre>\n
     <\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem A positive integer\u00a0is\u00a0magical\u00a0if it is divisible by either\u00a0A\u00a0or\u00a0B. Return the\u00a0N-th magical number.\u00a0 Since the answer may be very large,\u00a0return it modulo\u00a010^9 + 7. Example…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[49],"tags":[52,359,217,360,31],"class_list":["post-3359","post","type-post","status-publish","format-standard","hentry","category-math","tag-binary-search","tag-gcd","tag-hard","tag-lcm","tag-math","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3359","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=3359"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3359\/revisions"}],"predecessor-version":[{"id":3363,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3359\/revisions\/3363"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3359"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3359"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3359"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}