求給定範圍內的最大公約數

問題表明我們需要找到給定範圍內的 GCD。我們將得到兩個正整數 x 和 y 以及兩個整數 p 和 q，其範圍為 [p,q]。我們需要找出落在 [p,q] 範圍內的數字 x 和 y 的 GCD（最大公約數）。 GCD，在數學中稱為最大公約數，是兩個給定正整數相除的最大正整數。給定的整數不得為零。對於任兩個正整數 x 和 y，它表示為 gcd(x,y)。

例如，我們有兩個正整數 6 和 9。最大公約數 gcd(6,9) 將為 3，因為它是除以這兩個數字的最大數。

但是在這個問題中，我們需要找到兩個給定的在指定範圍內的正整數的最大公約數。讓我們透過例子來理解這個問題。我們將得到 4 個數字作為輸入 x 和 y 來找出這些數字的 gcd 和兩個指示 gcd 範圍的數字，即 [p,q]。

輸入：x=8、y=12、p=1、q=3

輸出：2

解釋 - 由於給定的兩個數字 x 和 y 的最大公約數是 4。但 4 不在範圍 [1,3] 之內。 [1,3] 範圍內的最大公約數是 2，這是我們所需的輸出。

輸入：x=17、y=15、a=5、b=10

#輸出：-1

#解釋 - 數字 17 和 15 的最大公約數是 1。因為 1 不在給定範圍 [5,10] 內。當給定範圍內沒有公約數時，我們需要列印 -1 作為輸出。

演算法

我們用來解決問題的演算法非常簡單且與數學相關。首先，我們將找到數字 x 和 y 的 gcd（最大公約數）。在 C 中，有一個名為 gcd() 的內建函數，它會傳回數字的最大公約數作為輸出。

文法

int divisor=gcd(x,y);

我們也可以使用歐幾裡得演算法的有效方法來找出兩個數字的 gcd。兩者同時工作，時間複雜度為 O(log(min(x,y))。

現在，我們可以使用簡單的算術定律來得出結論：除以兩個數字的 gcd 的數字也將除以這兩個數字本身。因此，在 for 迴圈中從 i=1 迭代到 sqrt(gcd(x,y)) 將幫助我們獲得該數字的所有公約數。

然後，檢查每個 i 直到 sqrt(gcd(x,y)) i 是否整除 gcd(x,y)。如果 i 除以 gcd(x,y)，那麼我們可以說 gcd(x,y)/i 也將是 gcd 的除數，從而得出結論，它也是數字 x 和 y 的公約數。

讓我們透過一個例子來理解這個概念。假設 x 和 y 分別為 32 和 48。 gcd(18,27) 為 16。所以在這種情況下，我們將從 i=1 迭代到 i<=4，即 sqrt(16)。讓我們考慮 i=2。這裡我除以 gcd(18,27)，即 16/2，等於 8。因此 gcd(x,y)/i 也會除 gcd(x,y) 得到 i。 <=4，即 sqrt(16)。让我们考虑 i=2。这里我除以 gcd(18,27)，即 16/2，等于 8。因此 gcd(x,y)/i 也会除 gcd(x,y) 得到 i。

注意 - 如果數字n 除以任一數字x 得到y，可以表示為$\frac{n}{x}\:=\:y$ 那麼y 將n 除以x $ (x\:\times\:y\:=\:n)$。

該演算法可能是解決該問題的最有效方法。在遵循這個演算法的同時，我們將不斷檢查公約數是否在 [a,b] 範圍內。如果不正確，我們將使用 max() 函數不斷更新變數中的除數，以獲得範圍內的最大公約數。

max() 函數的語法

int m = max(a,b);

它傳回 a 和 b 的最大值。

方法

以下是我們將遵循的方法 -

• 初始化一個函數來計算給定範圍內的最大公約數。

• 計算兩個給定正數 x 和 y 的 gcd。

• 初始化變數名稱 ans = -1。

• 在 for 迴圈中從 i=1 迭代到 i<=sqrt(gcd(x,y)) 並不斷檢查 i 是否整除 gcd(x,y)。 <=sqrt(gcd(x,y)) 并不断检查 i 是否整除 gcd(x,y)。

• 如果(gcd(x,y)%i)=0，檢查i 是否在[a,b] 範圍內，以及是否使用max() 函數將其儲存在ans 中，以便我們得到最大公約數位於該範圍內。

• 同時檢查 gcd/i 是否在範圍內，如果在範圍內，則再次使用 max() 函數更新 ans 的值。

• 完成 for 迴圈中的所有迭代後傳回 ans。

範例

該方法在 C 中的實作 -

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

// to calculate gcd of two numbers using Euclidean algorithm
int gcd(int a, int b){
   if(a == 0)
   return b;
   return gcd(b % a, a);
}

//function to calculate greatest common divisor in the given range [a,b]
int build(int x, int y, int a, int b) {

   //using C++ inbuilt library to calculate gcd of given numbers
   int z = gcd(x, y); //we can use euclidean algorithm too as an alternative
   int ans = -1; //storing -1 for the case when no common divisor lies in the range
   for(int i = 1; i<=sqrt(z); i++) { //iterating until sqrt(z) because either of two factors
      //of a number must be less than square root of the number
      if(z % i == 0) {
         if(i >= a && i <= b) //checking it i lies in the range
         ans = max(ans, i); //storing maximum value
         if((z / i) >= a && (z / i) <= b)
         ans = max(ans, z / i);
      }
   }
   return ans;
}
int main() {
   int x, y, a, b;
   x=24, y=42, a=3, b=9;
   cout << build(x, y, a, b) <<" is the gcd that lies in range ["<<a<<","<<b<<"]"<<endl;
   return 0;
}

輸出

6 is the gcd that lies in range [3,9]

時間複雜度：O(log(min(x,y)) sqrt(z))，其中 z 是兩個數字 x 和 y 的最大公約數。

空間複雜度：O(1)，因為沒有使用額外的空間。

結論

我們討論了求解 [a,b] 範圍內兩個數的 gcd 問題的方法。這就是我們如何在 C 中使用各種不同的函數來解決上述問題。

我希望您覺得這篇文章很有幫助，並澄清您與該問題有關的所有概念。

以上是求給定範圍內的最大公約數的詳細內容。更多資訊請關注PHP中文網其他相關文章！