FilesExpand file tree

 master

/

878.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

24 lines (19 loc) · 514 Bytes

 master

/

878.py

Copy path

Top

File metadata and controls

• Code
• Blame

24 lines (19 loc) · 514 Bytes

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:

def nthMagicalNumber(self, N: int, A: int, B: int) -> int:

def gcd(x, y):

if not x:

return y

else:

return gcd(y % x, x);

A_B = A*B//gcd(A, B)

MOD = 10**9 + 7

i = 1

j = 10 ** 15

while i < j:

mid = (i + j) // 2

n = mid // A + mid // B - mid // A_B

if n < N:

i = mid + 1

else:

j = mid

return i % MOD