nth-magical-number

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

A positive integer is magical if it is divisible by either <code>a</code> or <code>b</code>.

Given the three integers <code>n</code>, <code>a</code>, and <code>b</code>, return the <code>nth</code> magical number. Since the answer may be very large, return it modulo <code>109 + 7</code>.

&nbsp;
Example 1:

<pre>
Input: n = 1, a = 2, b = 3
Output: 2
</pre>

Example 2:

<pre>
Input: n = 4, a = 2, b = 3
Output: 6
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= n &lt;= 109</code></li>
	<li><code>2 &lt;= a, b &lt;= 4 * 104</code></li>
</ul>

nthMagicalNumber

Nth Magical Number

Math

Binary Search

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

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

&nbsp;

<ol>
</ol>

示例 1：

<pre>
输入：n = 1, a = 2, b = 3
输出：2
</pre>

示例&nbsp;2：

<pre>
输入：n = 4, a = 2, b = 3
输出：6
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= n &lt;= 109</code></li>
	<li><code>2 &lt;= a, b &lt;= 4 * 104</code></li>
</ul>

&nbsp;