c++ - 使用除法技术求数组的最大公约数

Question

我正在尝试查找数组的 GCD/HCF，我知道编写使用欧几里得算法查找两个数字的 GCD 的函数。因此，为了找到数组的 GCD，我想使用欧几里得算法作为 GCD 数组的分而治之技术。我成功地能够划分它，但坚持使用合并函数再次执行 GCD 操作，我正在为这种情况下的合并函数(即征服部分)寻求帮助。

我的代码是这样的；

#include <iostream>
using namespace std;
long long GCD(long long  m,long long n)
{
    while(m%n!=0)
    {
        long long next_m=n;
        long long next_n=m%n;
        m=next_m;
        n=next_n;
    }
    return n;
}
//define merge function.
long long hcf_arr(long long *arr,long long start,long long end){
    if(end-start+1==2){
        return GCD(arr[start],arr[end]);
    }
    else{
        long long *u;
        u=new long long[(end-start+1)/2];
        long long *v;
        v=new long long[(end-start+1)-(end-start+1)/2];
        for(long long i=start;i<=(end-start+1)/2;i++){
            u[i]=arr[i];
        }
        for(long long i=(end-start+1)/2+1;i<=(end-start+1);i++){
            v[i]=arr[i];
        }
        hcf_arr(u,start,(end-start+1)/2);
        hcf_arr(v,(end-start+1)/2+1,end-start+1);
        //Merge function

    }

}

int main() {
    
}

Answer 1

您可以找到左右子数组的 GCD，并计算这两个子数组的 GCD。这是可行的，因为如果将任何数字替换为包含该数字的任何子数组的 GCD，则数字列表的 GCD 保持不变。

仅供引用，这个std::reduce(arr.begin(),arr.end(),arr[0],GCD);有一个很好的单行代码。。

几点:

1. 我看到 new 和 delete 语句的数量不等，这不好。使用std::vector。
2. 那些 for 循环可以替换为 std::copy
3. 前两个步骤可以与 std::vector 的基于范围的构造函数结合使用。
4. 由于您不修改数组，因此将它们标记为 const。