在一個區間內的最大公約數

設 x 和 y 為兩個數字。在這種情況下，如果當 y 除以 x 時傳回零餘數，則稱 x 是 y 的除數。區間中出現的最大除數是該區間最大元素數的除數。

問題陳述

給定一個區間 [a, b]。求出包含 a 和 b 的範圍內（除了「1」之外）出現的最大除數。如果所有除數出現次數相同，則傳回 1。

範例 1

Input [2, 5]

Output 2

解釋 - 2 的約數= {1, 2}，3 的約數= {1, 3}，4 的約數= {1, 2, 4}，5 的約數= {1 , 5}。 2 是出現次數最多的除數。

範例 2

Input [2, 5]

Output 2

解釋 - 2 的約數= {1, 2}，3 的約數= {1, 3}，4 的約數= {1, 2, 4}，5 的約數= {1 , 5}。 2 是出現次數最多的除數。

方法 1：暴力破解

解決這個問題的強力方法是找到區間內所有數字的所有約數，並將它們連同出現的次數一起儲存在映射中。

演算法

過程除數（num）

• 對於 i = 1 到 n1/2 1

• #如果 num%i == 0

• 如果 num/i == i

• 如果 i 不在地圖中，則插入 (i, 1)

• 否則映射[i]

• #其他

• 如果 i 不在地圖中，則插入 (i, 1)

• 否則映射[i]

• #如果 num/i 不在地圖中，則插入 (num/i, 1)

• #其他地圖[num/i]

過程 maxDivisors (a, b)

• 對於 n = a 到 b

• 除數 (n)

• #map.erase(1)

• 除數 = 1，計數 = int_min

• #對於地圖中的每個元素

• if it.value > 計數

• 計數 = it.value

• 除數 = it.key

範例：C 實作

在下面的程式中，我們在 divisors() 函數中找出每個數字的約數，並在 maxdivisor() 函數中找出最大出現的除數。

#include <bits/stdc++.h>
using namespace std;

// map storing occurrence of each divisor
unordered_map<int, int> occ;

// function to find all the divisors of a number and store it in map
void divisors(int num){
   for (int i = 1; i <= (sqrt(num) + 1); i++)    {
   
      // checking if i is divisor of num
      if (num % i == 0)        {
      
         // checking if num has identical divisors i.e. if i*i == num
         // if identical divisors then save only one
         if (num / i == i) {
            if (occ.find(i) == occ.end()) {
               occ.insert(make_pair(i, 1));
            }
            else{
               occ[i]++;
            }
         }
         else{
         
            // saving divisor i
            if (occ.find(i) == occ.end()) {
               occ.insert(make_pair(i, 1));
            }
            else{
               occ[i]++;
            }
            
            // saving the divisor of num corresponding to i
            if (occ.find(num / i) == occ.end()) {
               occ.insert(make_pair(num / i, 1));
            }
            else{
               occ[num / i]++;
            }
         }
      }
   }
}

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){
   for (int n = a; n <= b; n++){
      divisors(n);
   }
   
   // deleting all occurrences of 1 as 1 is not to be returned until the interval is [1,1]
   occ.erase(1);
   
   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++) {
      if (it->second > cnt) {
         cnt = it->second;
         div = it->first;
      }
   }
   return div;
}
int main(){
   int a = 4, b = 7;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

輸出

For the interval [4, 7] maximum occurring divisor = 2

時間複雜度 - O(n3/2)，因為對於區間中的每個數字，為了找出除數，執行複雜度為 O(n1/2) 的迴圈。

空間複雜度 - O(n)，地圖空間。

方法 2

可以透過減少用每個除數的出現來填充映射的時間來進一步優化上述方法。不是找到每個數字的除數，而是可以透過計算區間的下限和上限來獲知區間中每個除數的出現情況。

讓我們以區間 [2, 5] 為例。

可能的約數集是從 1 到 5。因此，出現 1 = 5/1 - 2/1 1 = 4。出現 2 = 5/2 - 2/2 1 = 2。出現 3 = 5/3 - 2/3 = 1。出現 4 = 5/4 - 2/4 = 1。出現 5 = 5/5 - 2/5 = 1。

以上可以形式化為，

如果下界%除數 == 0 則 occ = 上界/除數 - 下界/除數 1

其他 occ = 上界/除數 - 下界/除數

演算法

過程 maxDivisor (a, b)

• 對於 i = 2 到 b

• 如果 a%i == 0

• 次數 = b/i - a/i 1

• #其他

• 次數 = b/i - a/i

• map.insert(i, 次)

• 除數 = 1，計數 = int_min

• #對於地圖中的每個元素

• if it.value > 計數

• 計數 = it.value

• 除數 = it.key

範例：C 實作

在下面的程式中，我們不是以相反的順序找出數字的除數，而是針對每個除數找出它在區間內有多少個倍數。

#include <bits/stdc++.h>
using namespace std;

// function to find maximum occurring divisor in an interval
int maxDivisor(int a, int b){

   // map used to store occurrences of divisors
   unordered_map<int, int> occ;
   for (int i = 2; i <= b; i++){
      int times;
      if (a % i == 0){
         times = (b / i) - (a / i) + 1;
      }
      else{
         times = (b / i) - (a / i);
      }
      occ.insert(make_pair(i, times));
   }

   // divisor set as 1 for edge case scenario when interval is [1,1]
   int div = 1, cnt = INT_MIN;
   for (auto it = occ.begin(); it != occ.end(); it++){
      if (it->second > cnt){
         cnt = it->second;
         div = it->first;
      }
   }
   return div;
}
int main(){
   int a = 1, b = 10;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

輸出

For the interval [1, 10] maximum occurring divisor = 2

方法 3

該問題的一個非常簡單的解決方案如下所示，

在任何大小 > 1 的區間中，一半的數字（每個偶數）將以 2 作為除數。

因此可以如下使用。

演算法

過程 maxDivisors (a, b)

• 如果 a == b

• #ans = a

• #其他

• ans = 2

#範例：C 實作

在下面的程式中，我們實作了每個偶數都有 2 作為約數的觀察結果。

#include <bits/stdc++.h>
using namespace std;

// function to find the maximum occurring divisor in an interval
int maxDivisor(int a, int b){
   if (a == b){
      return a;
   } else {
      return 2;
   }
}
int main(){
   int a = 1, b = 10;
   cout << "For the interval [" << a << ", " << b << "] maximum occurring divisor = ";
   cout << maxDivisor(a, b);
   return 0;
}

輸出

For the interval [1, 10] maximum occurring divisor = 2

結論

總之，為了找到一個區間內最大出現除數，我們可以使用上述方法，時間範圍從O(n3/2) 到O(1)，空間範圍從O(n) 到O( 1).

以上是在一個區間內的最大公約數的詳細內容。更多資訊請關注PHP中文網其他相關文章！