第 N 个神奇数字Java

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

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

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 10⁹
2 <= a, b <= 4 * 10⁴

# 思路

最小公倍数

# 解法

class Solution {
    public int nthMagicalNumber(int n, int a, int b) {
        int mod = (int)1e9+7;
        long lcm = (long)(a*b)/GCD(a,b);//最小公倍数
        long m = lcm/a + lcm/b - 1 , num = (lcm*(n/m))%mod;
        int k = n%(int)m, a_  = a , b_ = b;
        while(k > 1){
            if(a_ < b_) a_ += a;
            else b_ += b;
            k--;
        }
        return k == 0 ? (int)(num%mod) : (int)((num+Math.min(a_,b_))%mod);
    }
    private int GCD(int a, int b){
        return a%b == 0 ? b : GCD(b,a%b);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 总结

分析出几种情况，然后分别对各个情况实现

← 石子游戏盈利计划→