使用分治法的数组的最大公约数

Question

我正在尝试查找数组的 GCD/HCF，我知道使用 Euclid 算法编写函数来查找两个数字的 GCD。所以为了找到数组的 GCD，我想使用这个 Euclid 算法作为 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）。

    ...
    long long leftGCD = hcf_arr(u,start,(end-start+1)/2);
    long long rightGCD = hcf_arr(v,(end-start+1)/2+1,end-start+1);
    return GCD(leftGCD, rightGCD); //Merge function
} ...

Answer 2

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

仅供参考，这个 std::reduce(arr.begin(),arr.end(),arr[0],GCD);.

有一个很好的单线

两点：

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

使用分治法的数组的最大公约数

Greatest common diviser of an arrray using divide conquer technique

c++

arrays

recursion

function

divide-and-conquer