分数（或有理数）数组的最大公约数

---

最大公约数（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++ 程序。