题目

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

1
2
输入:N = 3, A = 6, B = 4
输出:8

提示:

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

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

/**
* Least Common Multiple
* 最小公倍数
* = 两数相乘 / 最大公约数
*/
func calcLcm(a, b int) int {
return a * b / calcGcd(a, b)
}

/**
* greatest common divisor 最大公约数
* 辗转相除法,很形象
*/
func calcGcd(a, b int) int {
c := a % b
for c != 0 {
a = b
b = c
c = a % b
}
return b
}

/**
* 数字相关的题目,很多都是寻找规律
* 两个数的神奇数字,每到最小公倍数的时候会重复一次,根据这个找到突破口
* 可以很容易算的每组有多少次A、有多少次B,有效次数是timesA + timesB - 1
* 两次最小公倍数之间划为一组,N / timesA + timesB - 1 和 N % timesA + timesB - 1 获取那一组,然后在这一组寻找即可
*/
func nthMagicalNumber(N int, A int, B int) int {
gcd := calcLcm(A, B)
perCircleALen, perCircleBLen := gcd / A, gcd / B
perCircleLen := perCircleALen + perCircleBLen - 1

circleIdx := N / perCircleLen

idxA, idxB := perCircleALen * circleIdx, perCircleBLen * circleIdx
nowNum := perCircleALen * circleIdx * A
N -= perCircleLen * circleIdx

for {
if N == 0 {
break
}

//
for idxA * A <= nowNum {
idxA++
}

for idxB * B <= nowNum {
idxB++
}

if idxA * A > idxB * B {
nowNum = idxB * B
idxB++
} else {
nowNum = idxA * A
idxA++
}

N--
}

return nowNum % 1000000007
}

参考

  1. leetcode地址:https://leetcode-cn.com/contest/weekly-contest-95/problems/nth-magical-number/