2023-05-17：一個(gè)正整數(shù)如果能被 a 或 b 整除，那么它是神奇的。

給定三個(gè)整數(shù) n , a , b ，返回第 n 個(gè)神奇的數(shù)字。

因?yàn)榇鸢缚赡芎艽螅苑祷卮鸢?對 10^9 + 7 取模 后的值。

輸入：n = 4, a = 2, b = 3。

輸出：6。

答案2023-05-17：

過程描述：

1.計(jì)算?a?和?b?的最小公倍數(shù)?lcm。

2.初始化變量?l?為0，變量?r?為?(n * min(a, b))，其中?min(a, b)?表示?a?和?b?中的最小值。在這個(gè)范圍內(nèi)通過二分查找獲得第?n?個(gè)神奇數(shù)字。

3.對于每個(gè)二分查找猜測值，計(jì)算在?a和b中出現(xiàn)的神奇數(shù)字個(gè)數(shù)：m/a + m/b。然后計(jì)算?a?和?b?的公共倍數(shù)?lcm?在?m?范圍內(nèi)出現(xiàn)的神奇數(shù)字個(gè)數(shù)：m/lcm。

4.如果出現(xiàn)的神奇數(shù)字總數(shù)大于或等于?n，則將當(dāng)前猜測值存儲(chǔ)在變量?ans?中，并將右邊界向左移動(dòng)一位（即縮小區(qū)間的范圍）。

5.如果出現(xiàn)的神奇數(shù)字總數(shù)小于?n，則將左邊界向右移動(dòng)一位（即擴(kuò)大區(qū)間的范圍），并繼續(xù)迭代。

6.二分查找過程結(jié)束后，返回答案?ans % (10^9 + 7)。

時(shí)間復(fù)雜度為 O(logN)，空間復(fù)雜度為 O(1)。

在這個(gè)算法中，使用了二分查找來搜索第?n?個(gè)神奇數(shù)字。在最壞情況下，二分查找的迭代次數(shù)為 O(logN)。因此，時(shí)間復(fù)雜度為 O(logN)。

另外，在算法中只使用了幾個(gè)整數(shù)變量來存儲(chǔ)值和計(jì)算結(jié)果，所以空間復(fù)雜度為 O(1)。

go完整代碼如下：

package?main

func?nthMagicalNumber(n?int,?a?int,?b?int)?int?{
????//?求a和b的最小公倍數(shù)
????lcm?:=?int64(a?/?gcd(a,?b)?*?b)
????var?ans?int64?=?0
????//?l?=?0
????//?r?=?(long)?n?*?Math.min(a,?b)
????l,?r?:=?int64(0),?int64(n)*int64(min(a,?b))
????for?l?<=?r?{
????????m?:=?(l?+?r)?/?2
????????if?m/int64(a)+m/int64(b)-m/lcm?>=?int64(n)?{
????????????ans?=?m
????????????r?=?m?-?1
????????}?else?{
????????????l?=?m?+?1
????????}
????}
????return?int(ans?%?1000000007)
}

func?gcd(a?int,?b?int)?int?{
????if?b?==?0?{
????????return?a
????}
????return?gcd(b,?a%b)
}

func?min(a?int,?b?int)?int?{
????if?a?<?b?{
????????return?a
????}
????return?b
}

func?main()?{
????n?:=?1000000000
????a?:=?40000
????b?:=?40000
????result?:=?nthMagicalNumber(n,?a,?b)
????println(result)
}


rust完整代碼如下：

fn?nth_magical_number(n:?i32,?a:?i32,?b:?i32)?->?i32?{
????let?n?=?n?as?i64;
????let?a?=?a?as?i64;
????let?b?=?b?as?i64;
????//?求a和b的最小公倍數(shù)
????let?lcm?=?a?/?gcd(a,?b)?*?b;
????let?mut?ans?=?0;
????//?l?=?0
????//?r?=?(long)?n?*?Math.min(a,?b)
????let?mut?l?=?0;
????let?mut?r?=?(n?*?std::cmp::min(a,?b));
????while?l?<=?r?{
????????let?m?=?(l?as?i64?+?r?as?i64)?/?2;
????????if?m?/?a?as?i64?+?m?/?b?as?i64?-?m?/?lcm?as?i64?>=?n?as?i64?{
????????????ans?=?m;
????????????r?=?m?-?1;
????????}?else?{
????????????l?=?m?+?1;
????????}
????}
????(ans?%?1000000007)?as?i32
}

fn?gcd(a:?i64,?b:?i64)?->?i64?{
????if?b?==?0?{
????????a
????}?else?{
????????gcd(b,?a?%?b)
????}
}

fn?main()?{
????let?n?=?1000000000;
????let?a?=?40000;
????let?b?=?40000;
????let?result?=?nth_magical_number(n,?a,?b);
????println!("{}",?result);
}


c語言完整代碼如下：

#include?<stdio.h>

long?long?gcd(long?long?a,?long?long?b)?{
????return?b?==?0???a?:?gcd(b,?a?%?b);
}

int?nthMagicalNumber(int?n,?int?a,?int?b)?{
????//?求a和b的最小公倍數(shù)
????long?long?lcm?=?(long?long)a?/?gcd(a,?b)?*?b;
????long?long?ans?=?0;
????//?l?=?0
????//?r?=?(long)?n?*?Math.min(a,?b)
????for?(long?long?l?=?0,?r?=?(long?long)n?*?(a?<?b???a?:?b),?m?=?0;?l?<=?r;)?{
????????m?=?(l?+?r)?/?2;
????????if?(m?/?a?+?m?/?b?-?m?/?lcm?>=?n)?{
????????????ans?=?m;
????????????r?=?m?-?1;
????????}
????????else?{
????????????l?=?m?+?1;
????????}
????}
????return?(int)(ans?%?1000000007);
}

int?main()?{
????int?n?=?1000000000;
????int?a?=?40000;
????int?b?=?40000;
????int?result?=?nthMagicalNumber(n,?a,?b);
????printf("%d\n",?result);
????return?0;
}


c++完整代碼如下：

#include?<iostream>
using?namespace?std;

long?long?gcd(long?long?a,?long?long?b)?{
????return?b?==?0???a?:?gcd(b,?a?%?b);
}

int?nthMagicalNumber(int?n,?int?a,?int?b)?{
????//?求a和b的最小公倍數(shù)
????long?long?lcm?=?(long?long)a?/?gcd(a,?b)?*?b;
????long?long?ans?=?0;
????//?l?=?0
????//?r?=?(long)?n?*?Math.min(a,?b)
????for?(long?long?l?=?0,?r?=?(long?long)n?*?min(a,?b),?m?=?0;?l?<=?r;)?{
????????m?=?(l?+?r)?/?2;
????????if?(m?/?a?+?m?/?b?-?m?/?lcm?>=?n)?{
????????????ans?=?m;
????????????r?=?m?-?1;
????????}
????????else?{
????????????l?=?m?+?1;
????????}
????}
????return?(int)(ans?%?1000000007);
}

int?main()?{
????int?n?=?1000000000;
????int?a?=?40000;
????int?b?=?40000;
????int?result?=?nthMagicalNumber(n,?a,?b);
????cout?<<?result?<<?endl;
????return?0;
}


福大大架構(gòu)師每日一題

java當(dāng)死，golang當(dāng)立。最新面試題，涉及golang，rust，mysql，redis，云原生，算法，分布式，網(wǎng)絡(luò)，操作系統(tǒng)。

511篇原創(chuàng)內(nèi)容

公眾號(hào)