分數（或有理數）陣列的最大公約數

---

最大公約數（HCF）是指能夠同時整除兩個或多個數字的最大數字。

有理數是兩個數字的商 p/q，其中 q 不等於 0。

問題陳述

給定一個包含分數的陣列，求這些數字的最大公約數。

示例 1

輸入

[{4, 5}, {10, 12}, {24, 16}, {22, 13}]

輸出

{2, 3120}

解釋

給定的分數為：4/5、10/12、24/16 和 22/13

2/3120 是能同時整除所有這些分數的最大數。

示例 2

輸入

[{18, 20}, {15, 12}, {27, 12}, {20, 6}]

輸出

{3, 1400}

解釋

給定的分數為：18/20、15/12、27/12 和 20/6

1/60 是能同時整除所有這些分數的最大數。

方法

要查詢分數的最大公約數，請執行以下步驟：

• 計算分子的最大公約數。

• 計算分母的最小公倍數。

• 計算最大公約數/最小公倍數。

• 如果可能，將分數約簡到最簡分數。

讓我們將上述方法分解成兩部分：

查詢分子的最大公約數

為了查詢兩個數字的最大公約數，使用歐幾里得演算法。

該演算法使用以下事實：

• 如果我們將較小的數字從較大的數字中減去，則兩個數字的最大公約數不會改變。因此，如果我們不斷地從兩個數字中較大的數字中減去較小的數字，最終得到最大公約數。

• 我們可以使用除法代替減法。如果我們除以較小的數字，當餘數變為 0 時，演算法停止。

查詢兩個數字的最大公約數的 C++ 函式

//Function to find HCF of two numbers
int HCF(int a, int b)
{
   if (a % b == 0)
      return b;
   else
      return (HCF(b, a % b));
}

現在，我們可以迭代地找到整個陣列（多於兩個數字）的分子的最大公約數。

//Function to find HCF of the numerator series
int findHcf(vector<pair<int,int>>v)
{
   int hcf = v[0].first;
   for (int i = 1; i < v.size(); i++)
      hcf = HCF(hcf, v[i].first);
   // return hcf of the numerators
   return (hcf);
}

查詢分母的最小公倍數

為了查詢兩個數字 a 和 b 的最小公倍數，我們可以使用以下公式：

LCM(a,b) * HCF (a,b) = a*b
Hence, LCM(a,b) = (a*b) / HCF(a,b) 

現在，我們可以迭代地找到整個陣列（多於兩個數字）的分母的最小公倍數。

查詢分母的最小公倍數的 C++ 函式

//Function to find lcm of the denominator series
int findLcm(vector<pair<int,int>>v)
{
    // ans contains LCM of arr[0][1], ..arr[i][1]
    int lcm = v[0].second;
    for (int i = 1; i < v.size(); i++)
        lcm = (((v[i].second * lcm)) /
            (HCF(v[i].second, lcm)));
    // return lcm of the denominator
    return (lcm);
}

• 步驟 1 - 初始化一個對向量：vector<pair<int,int>>vec

• 步驟 2 - 將分數輸入到 vec 中

• 步驟 3 - ans -> find_hcf_of_fraction(vec)

• 步驟 4 - 列印 ans

虛擬碼

Function find_hcf_of_fraction(vec):
   HCF_of_num -> findHCF(vec)
	LCM_of_denom -> findLCM(vec)

	Initialize vector ans: vectorans;
	ans -> [Hcf_of_num, Lcm_of_num]
	For i = ans[0]/2 to 2:
		if (ans[1] % i == 0) and (ans[0] % i == 0):
			ans[1] -> ans[1]/i
			ans[0] -> ans[0]/i
	
	return ans

Function find_HCF(vec):
	hcf -> vec[0].first
	For i=0 to vec.size()-1:
		hcf -> HCF(ans, vec[i].first)
	return ans

Function HCF(a,b):
	if a%b->0:
		return a
	else:
		return HCF(b , a%b)

Function findLCM(vec):
	lcm -> vec[0].second
	For i=0 to vec.size()-1:
		lcm-> (lcm* vec[i].second) / (hcf (vec[i].second, lcm))
	return lcm

示例（C++ 程式）

下面是一個 C++ 程式，用於查詢有理數（分數）陣列的最大公約數。

#include <bits/stdc++.h>
using namespace std;
//Function to find HCF of two numbers
int HCF(int a, int b){
   if (a % b == 0)
      return b;
   else
      return (HCF(b, a % b));
}
//Function to find HCF of the numerator series
int findHcf(vector<pair<int,int>>v){
   int hcf = v[0].first;
   for (int i = 1; i < v.size(); i++)
      hcf = HCF(hcf, v[i].first);
   // return hcf of the numerators
   return (hcf);
}
//Function to find lcm of the denominator series
int findLcm(vector<pair<int,int>>v){
   // ans contains LCM of arr[0][1], ..arr[i][1]
   int lcm = v[0].second;   
   for (int i = 1; i < v.size(); i++)
      lcm = (((v[i].second * lcm)) /
         (HCF(v[i].second, lcm)));
   // return lcm of the denominator
   return (lcm);
}
//Function to get the answer
vector<int> find_hcf_of_fraction(vector<pair<int,int>>v){
   //HCF of the numerator series
   int hcf_of_num = findHcf(v);
   // lcm of the denominator series
   int lcm_of_deno = findLcm(v);
   vector<int>ans(2);
   ans[0] = hcf_of_num;
   ans[1] = lcm_of_deno;
   for (int i = ans[0] / 2; i > 1; i--)    {
      if ((ans[1] % i == 0) && (ans[0] % i == 0))        {
         ans[1] /= i;
         ans[0] /= i;
      }
   }
   // return answer
   return (ans);
}
//main code
int main(){
   int size = 4;
   vector<pair<int,int>>vec;
   //Inserting the fractions in the vector
   vec.push_back({4,5});
   vec.push_back({10,12});
   vec.push_back({24,16});
   vec.push_back({22,13});
   //Function call to calculate the HCF of the fractions
   vector<int>ans;
   ans = find_hcf_of_fraction(vec);
   //Print the answer
   cout << "HCF of given array of fractions: ";
   cout << "{" << ans[0] << ", " << ans[1] << "}"<< endl;
   return 0;
}

輸出

對於輸入 - [{4, 5}, {10, 12}, {24, 16}, {22, 13}]，上述 C++ 程式將產生以下輸出：

HCF of given array of fractions: {2, 3120}

結論

本文討論了查詢分數最大公約數的問題。文章中涵蓋的內容包括方法、虛擬碼和 C++ 程式。