大小為 k 的子序列的最大可能最大公約數

---

問題陳述中說，我們將得到一個數組作為輸入和一個正整數 K，我們需要在這個問題中找出陣列的 k 大小子序列的最大可能最大公約數（最大公約數）。可以使用不同的演算法來求數字的最大公約數，並找出 k 大小子序列的最大公約數。

在此之前，我們必須瞭解陣列的子序列。陣列的子序列是陣列中數字的一個序列，這些數字不一定是陣列中的相鄰數字，但序列中數字的順序必須與它們在陣列中的順序相同，才能被稱為陣列的子序列。子序列在本質上可能是連續的，也可能是不連續的。

例如，a=[1,2,3,4,5,6]。[1, 2, 5] 是陣列 a 的一個子序列。在這個問題中，我們需要找到陣列 a[] 的大小為 K 的正確子序列，使得該子序列的最大公約數是在所有大小為 K 的子序列中最大可能的公約數。透過以下示例可以更好地理解該問題：

輸入：a=[5, 2, 6, 10, 12]，K=2

輸出 : 6

說明：6 是大小為 K（即 2）的子序列的最大可能最大公約數。6 是 [6,12] 的最大公約數。也可能存在其他子序列，例如 [5,10]、[10,12] 等等。但 [5,10] 的最大公約數是 5，[10,12] 的最大公約數是 2。因此，6 是所有大小為 2 的子序列中最大可能的公約數。

輸入：a=[1,2,3,4,5]，K=3

輸出 : 1

說明：給定子序列的大小為 3。任何大小為 3 的可能子序列的最大公約數都只有 1。因此，1 是我們的輸出。

讓我們看看可以用來解決此問題的演算法。

演算法

解決此問題的樸素方法可以是生成所有可能的 k 大小子序列，然後計算每個子序列的最大公約數。在所有計算出的最大公約數中找到的最大公約數將是我們的答案。由於該演算法僅適用於小型陣列，因此我們不能將其用作解決此問題的方法。

解決此問題的有效方法可以是：

• 我們將建立一個大小等於陣列中最大元素+1 的陣列。

• 我們可以使用 C++ 中內建的 *max_element() 函式找到陣列中存在的最大元素，該函式返回給定範圍內的最大元素。

語法

int x= *max_element(arr, arr+n); //n is the size of the array

• 我們將在給定陣列中從 i=0 到 i=array.size() 的 for 迴圈中迭代，以計算陣列中每個元素的除數個數。

• 在巢狀的 for 迴圈中從 j=1 到 sqrt(a[i]) 迭代，因為在數學中，每個有兩個因子的數字都至少有一個因子小於該數字的平方根。

• 如果 j 可以整除數字 a[i]，則透過向其新增 1 來更新我們在 j 索引處建立的陣列中的值。然後，如果它不等於 j，則還將陣列中 (a[i]/j) 索引處的值更新為 1，因為如果 j 可以整除 a[i] 得到某個數字，則該數字也將是 a[i] 的除數 (a[i]/j=x 或 a[i]/x=j)。

• 最後，在迭代給定陣列中的所有元素後，我們將迭代我們建立並存儲值的陣列。從最後一個元素迭代陣列並檢查該索引處的值是否大於或等於 K。

• 如果在從後向前迭代時，任何索引處的值都大於或等於 K，則該索引將是我們所需的答案，因為陣列中任何索引處的每個數字都表示給定陣列中索引值可以整除的元素的數量。因此，從後向前迭代將為我們提供可以整除給定陣列中 K 個或更多數字的最大可能數字。

現在讓我們在我們的方法中實現此演算法來解決問題。

方法

我們將遵循以下步驟來解決上述問題：

• 初始化一個函式來計算大小為 K 的子序列的最大可能最大公約數。

• 將給定陣列的最大元素儲存在變數 m 中。

• 建立一個大小為 m+1 的陣列，count[m+1]。

• 在 for 迴圈中從 i=0 迭代到陣列的大小。

• 在巢狀的 for 迴圈中，從 j=1 迭代到 sqrt(a[i]) 並檢查 j 的每個值，以檢視它是否可以整除 a[i]。

• 如果可以整除，則將 count 中 j 索引處的值增加 1。還要檢查 j 是否不等於 (a[i]/j)，如果是，則將 (a[i]/j) 索引處的值也增加 1。

• 然後，在所有迭代完成後，再次迭代更新所有所需值後的 count。

• 從後向前迭代 count，直到 i 大於或等於 1，因為 0 不能整除任何數字。我們遇到的第一個值大於或等於 K 的索引，該索引值將是我們的答案。

• 返回該索引作為輸出。

示例

在 C++ 中實現該方法：

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//function to calculate maximum gcd possible of subsequence of size K
int maximum_gcd(int a[], int N, int K){
   int m = *max_element(a,a+N); //store maximum element present in the array
   int count[m+1]={0}; //create an array to store count of every divisor
   for(int i=0;i<N;i++){ //iterate in the given array
      for(int j=1;j<=sqrt(a[i]);j++){ //to get every possible divisor of the given number in the array
         if(a[i]%j==0){
            //if it is a divisor of the number, update the count
            count[j]=count[j]+1;
            if(a[i]/j != j){ //a[i]/j is also the divisor of the number if j divides a[i]
               count[a[i]/j] = count[a[i]/j] + 1;
            }
         }
      }
   }
   int ans; //to store maximum gcd of subsequence of size K
   for(int i=m;i>=1;--i){ //iterating from to get the maximum value
      if(count[i]>=K){ //if value at index is greater than or equal to K
         ans = i; //the index must be the gcd of atleast one K-sized subsequence
         break;
      }
   }
   return ans; //return the answer
}
int main(){
   int a[]={8,10,3,15,20,9};
   int K=3;
   int N = sizeof(a)/sizeof(a[0]); //to calculate the size of the given array
   cout<<maximum_gcd(a,N,K)<<endl;
   return 0;
}

輸出

5

時間複雜度：O(𝑁 × 𝑠𝑞𝑟𝑡(𝑚))，其中 N 是給定陣列的大小，m 是陣列中存在的最大元素。

空間複雜度：O(m+1)，其中 m 是給定陣列中存在的最大元素。

結論

我們討論了使用不同的函式和方法在 C++ 中解決查詢大小為 K 的子序列的最大可能最大公約數（最大公約數）的問題。從樸素方法到有效方法，我們討論瞭如何在 C++ 中解決上述問題。

希望本文能幫助您解決您對該問題的理解。