我正在練習編碼挑戰，但我遇到了這個問題。
A 和他的朋友從整數商店各買了一個數字，A 有數字 N，他的朋友有數字 M。A 希望他們的數字應該是互質數。為了實作這一點，A 將這兩個數字除以可以同時整除這兩個數字的最大數字。做完這個操作后，A 想知道數字的總和，幫助他找到那個總和。
輸入
Input:
N = 6, M = 5
Output:
11
Explanation:
The largest number that can divide both
5 and 6 is 1.
After dividing, 5 6 = 11.
我試過這段代碼
long sum(long N, long M){
long divider = 1;
long min = Math.min(N,M);
for(long i=2; i<=min; i )
if(N%i==0 && M%i==0)
divider=i;
return (N/divider) (M/divider);
}
但預期的運行時復雜度為 O(log(n))。但是我的代碼給出了 O(n)。
我找不到任何方法使它成為對數。請任何幫助我。????
uj5u.com熱心網友回復：
您應該使用任何有效的演算法來找到GCD-Greatest Common Divisor。例如，您可以嘗試具有時間復雜度的歐幾里得演算法。O(log(min(N, M))
public static long sum(long N, long M) {
long gcd = gcdEuclideanAlgorithm(N, M);
return (N / gcd) (M / gcd);
}
private static long gcdEuclideanAlgorithm(long a, long b) {
return b == 0 ? a : gcdEuclideanAlgorithm(b, a % b);
}
您可以在此處找到更多演算法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/420790.html
標籤：