我如何确切地解决这个GCD？

Question

https://www.codechef.com/problems/maxgcd

Chef有一个由N个整数组成的集合。如果子集有两个或更多的元素，则Chef将该集合的子集称为良好的。他把所有的好子集表示为S1,S2,S3,…,S2n-n-1。现在他把每个好子集Si的元素的GCD表示为Gi。厨师想要找到最大的GI。

输入

输入的第一行包含一个表示测试用例数量的整数T。测试用例的描述如下：“每个测试用例的第一行包含一个表示集合中元素的个数的整数N，第二行包含N个空格分隔的整数A1，A2，...，AN表示集合中的元素。

输出

对于每个测试用例，输出最大Gi

我的解决方案：

1. 生成给定集的所有可能子集。
2. 使用欧几里得算法计算每个集合的GCD
3. 我试着找到所有这些的最大值。

这是我制作所有可能子集的代码：

vector< vector<int> > getAllSubsets(vector<int> set)
{
    vector< vector<int> > subset;
    vector<int> empty;
    subset.push_back( empty );

    for (int i = 0; i < set.size(); i++)
    {
        vector< vector<int> > subsetTemp = subset;

        for (int j = 0; j < subsetTemp.size(); j++)
            subsetTemp[j].push_back( set[i] );

        for (int j = 0; j < subsetTemp.size(); j++)
            subset.push_back( subsetTemp[j] );
    }
    return subset;
}

然而，我得到了TLE当与这种方法。我在这件事上哪里错了？

Answer 1

一个优化是，您永远不需要考虑大于2个元素的子集。这是因为如果你再添加一个元素，GCD只能减少。

这将导致O(n^2)算法。问题语句说n可以大到100000，所以我们需要做得更好。

问题还说，给定的值最多为500 000，因此GCD不能超过这个值。

设count[i]=值i在数组中出现的次数。

然后我们可以应用类似于埃拉托色尼的筛子的东西：对于一个固定值v，看看你是否能找到v的两个倍数(sum of count[multiple_of_v]>1)。如果可以，那么您可以拥有v的GCD。跟踪你能找到的最大值。

伪代码：

V = max(given array)
cnt[i] = how many times value i occurs in given array

for v = V down to 1:
  num_multiples_v = 0
  for j = v up to V:
    num_multiples_v += cnt[j]

  if num_multiples_v > 1: # TODO: break the inner loop when this is true
    print v as solution
    return

复杂度将是O(VloglogV)，应该很快。