878. Nth Magical Number

878. Nth Magical Number

难度: Hard

刷题内容

原题连接

内容描述

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 = 1, A = 2, B = 3
Output: 2
Example 2:

Input: N = 4, A = 2, B = 3
Output: 6
Example 3:

Input: N = 5, A = 2, B = 4
Output: 10
Example 4:

Input: N = 3, A = 6, B = 4
Output: 8


Note:

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

解题方案

思路 1
- 时间复杂度: O(A+B)- 空间复杂度: O(1)

数学题直接看的solution

  • 从数据范围看来,N高达10^9,直接遍历不现实
  • 注意到魔法数是有循环的,我们令P=A和B的最小公倍数,那么在每P个数中,魔法数的数量和位置都是相同的,因此我们只需要计算[1,p]中间的魔法数
  • [1,p]的魔法数数量是 P/A+P/B-1,注意到,P是A和B的最小公倍数,因此[1,p]中,既能被A整除,也能被B整除,只有一个数,就是P
  • 现在问题变成,在[1,p]中,求第n个魔法数

注意到,我们在[1,p]中任取一个数x(x<p),[1,x]中魔法数的数量是x/A+x/B,注意这个是整除。

```python
class Solution(object):
def nthMagicalNumber(self, N, A, B):
"""
:type N: int
:type A: int
:type B: int
:rtype: int
"""
def gcd(a, b):
if b == 0:
return a

top Created with Sketch.