Leetcode 878. 第 N 个神奇数字

Posted on In ,

题目描述

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

 

示例 1： 

输入：n = 1, a = 2, b = 3
输出：2

示例 2： 

输入：n = 4, a = 2, b = 3
输出：6

 

提示：

  • 1 <= n <= 109
  • 2 <= a, b <= 4 * 104

 

解答

算不上 hard 差不多是 medium 。

就先按照最大公倍数找，之后余下的部分再从小到大一个一个找。

后面一个一个找的部分应该还能再用二分优化一下，以后有空再写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int nthMagicalNumber(int n, int a, int b) {
        int mod=1e9+7;
        long m=lcm(a,b),x=m/a,y=m/b,ans=0;
        ans=n/(x+y-1)*m%mod;
        n%=(x+y-1);
        long ans_res=0;
        x=y=1;
        while(n){
            if (x*a<y*b){
                ans_res=x*a%mod;
                x++;
            }
            else
            {
                ans_res=y*b%mod;
                y++;
            }
            n--;
        }
        return (ans+ans_res)%mod;
    }
};

Complexity

  • Time: \(O(max(a,b))\)

辗转相除法的复杂度应该近似是\(O(log(max(a,b)))\) * Space: \(O(1)\)