[Swift]LeetCode878.第N个神奇数字|NthMagicalNumber

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址： https://www.cnblogs.com/strengthen/p/10601072.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

A positive integer is magical if it is divisible by either A or B.

Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: N = 3
Output: 2

Example 2:

Input: N = 3
Output: 6

Example 3:

Input: N = 4
Output: 10

Example 4:

Input: N = 4
Output: 8

Note:

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

如果正整数可以被 A 或 B 整除，那么它是神奇的。

返回第 N 个神奇数字。由于答案可能非常大，返回它模 10^9 + 7 的结果。

示例 1：

输入：N = 1, A = 2, B = 3
输出：2

示例 2：

输入：N = 4, A = 2, B = 3
输出：6

示例 3：

输入：N = 5, A = 2, B = 4
输出：10

示例 4：

输入：N = 3, A = 6, B = 4
输出：8

提示：

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

Runtime: 4 ms

Memory Usage: 18.4 MB

 1 class Solution {
 2     func nthMagicalNumber(_ N: Int, _ A: Int, _ B: Int) -> Int {
 3         var a:Int = A
 4         var b:Int = B
 5         var tmp:Int = 0
 6         var l:Int = 2
 7         var r:Int = Int(1e14)
 8         var mod:Int = Int(1e9 + 7)
 9         while (b > 0)
10          {
11             tmp = a
12             a = b
13             b = tmp % b
14         }
15         while (l < r)
16         {
17             var m:Int = (l + r) / 2;
18             if m / A + m / B - m / (A * B / a) < N
19             {
20                 l = m + 1
21             }
22             else
23             {
24                 r = m
25             }
26         }
27         return Int(l % mod)
28     }
29 }