問題表明我們需要找到給定範圍內的 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() 函數不斷更新變數中的除數，以獲得範圍內的最大公約數。
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中文網其他相關文章！
