如何找到给定集合中某些数对的GCD

Question

我可以计算两个数字的GCD。给定一个集S={1,2,3,4,5}，我必须计算每对的GCD，比如{1,2}=1，{1,3}=1，｛1,4}=1，<1,5}=1，<2,3}=1，[2,4}=2，{2,5}=1等等=n<=10^9或更多，但我想更好地学习O（N*sqrt（N））解或更多。我想要每对的GCD。

Answer 1

基本欧几里得算法会有所帮助。

int gcd(int a, int b){
    if (a == 0)
        return b;
    return gcd(b%a, a);
}

有趣的是，如果你想找到整个集合的GCD。您所需要做的就是从获得的GCD中形成一个子集并迭代，除非只剩下最后一个元素。例如S={1,2,3,4,5} => S1={GCD(1,2) , GCD(3,4) , add 5 } => S2={GCD(1,1) , and 5 } => S3={GCD(1,5)} => 1

Answer 2

您可以使用欧几里得算法编写程序

查看查找GCD（1071462）的示例

GCD{1,2,3,4,5}=GCD{GCD{1,2}，GCD{3,4}}，5}

只使用欧几里得算法4次来计算给定集合S={1,2,3,4,5}的GCD

通过使用欧几里得，你唯一需要做的就是找到提醒，直到数字不可见。