資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學查詢指定範圍內的最大公約數 (GCD)
問題要求我們找到位於給定範圍內的最大公約數 (GCD)。我們將得到兩個正整數 x 和 y，以及兩個整數 p 和 q，它們表示範圍 [p,q]。我們需要找出 x 和 y 的最大公約數，並且這個最大公約數必須落在這個範圍 [p,q] 內。最大公約數 (GCD)，在數學中也稱為最大公因數，是能夠同時整除兩個給定正整數的最大正整數。給定的整數不能為零。對於任意兩個正整數 x 和 y，它表示為 gcd(x,y)。
例如，我們得到兩個正整數 6 和 9。它們的最大公約數 gcd(6,9) 為 3，因為它是能夠同時整除這兩個數的最大數。
但是在這個問題中，我們需要找到兩個給定正整數的最大公約數，並且這個最大公約數必須落在指定的範圍內。讓我們用例子來理解這個問題。我們將得到 4 個數字作為輸入：x 和 y（用於求這兩個數的最大公約數），以及兩個數字表示最大公約數的範圍，即 [p,q]。
輸入：x=8，y=12，p=1，q=3
輸出 : 2
解釋 – 給定兩個數 x 和 y 的最大公約數是 4。但是 4 不在範圍 [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);
我們也可以使用高效的歐幾里得演算法來查詢兩個數的最大公約數。兩者的時間複雜度相同，即 O(log(min(x,y)))。
現在，我們可以根據簡單的算術定律得出結論：能夠整除兩個數的最大公約數的數，也能同時整除這兩個數本身。因此，從 i=1 迭代到 sqrt(gcd(x,y)) 將幫助我們獲得該數的所有公約數。
然後，檢查從 1 到 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。這裡 i 整除 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 的最大公約數。
初始化一個名為 ans 的變數，其值為 -1。
從 i=1 迭代到 i<=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] 內的兩個數的最大公約數。這就是我們如何使用各種不同函式在 C++ 中解決上述問題。
我希望您覺得這篇文章有幫助，並能清除您對該問題的全部概念。
479 次瀏覽
