如何最大化 n 个正整数的 GCD，并从代表它们的序列中删除最少数量？

Question

我正在尝试解决一项竞争性编程任务，但我找不到有效的解决方案来解决最后 5 个测试用例。

你有 t (t >= 1 && t <= 5) 个查询，每个查询由 n 个数字 num (num >= 1 && num <= 1000000) 组成。表示每个查询的序列未排序，其中可以有重复的数字。所有ns的总和小于1000000，我们称一次查询中所有数字的GCD为x。任务是找出为了最大化 x 必须进行的最少移除次数。时间限制为 0.7 秒。

Consider 这 (8, 2, 6, 4, 10, 12) 是我得到的查询。 GCD (8, 2, 6, 4, 10, 12) = 2 但如果我删除 2、6 和 10 GCD (8, 4, 12) = 4。我将初始 GCD x 从 2 增加到 4，删除了 3 次，即 2 , 6 and 10. 本题答案为3.

到目前为止，我想到的最好的 ide 是以下几个：

#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <limits>
#include <algorithm>
#include <iterator>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    int i, n, tmp, j, num, div, max, min, rem;
    std::vector<int> ans;
    for (i = 0; i != t; ++i) {
        std::cin >> n;
        tmp = 0;
        std::map<int, int> buckets;
        for (j = 0; j != n; ++j) {
            std::cin >> num;
            tmp = std::gcd(tmp, num);
            for (div = 1; div * div <= num; ++div) {
                if (num % div == 0) {
                    ++buckets[div];
                    if (div * div != num) {
                        ++buckets[num / div];
                    }
                }
            }
        }
        max = tmp;
        min = std::numeric_limits<int>::max();
        for (auto const& elem : buckets) {
            if (elem.second != n && elem.first > max) {
                rem = n - elem.second;
                if (rem < min) {
                    max = elem.first;
                    min = rem;
                }
            }
        }
        ans.emplace_back(min);
    }
    std::copy(ans.cbegin(), std::prev(ans.cend()),
        std::ostream_iterator<int>(std::cout, "\n"));
    std::cout << ans.back() << '\n';
    return 0;
}

我正在计算 x (tmp) 并将每个数字 (num) 拆分为其 div 异构体 (div)。我不断更新存储桶，它是 std::map。我遍历 buckets 并找出哪个 divisor (elem.first) 大于 max (x) 并且同时导致最小移除次数。

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    int i, n, tmp_gcd, tmp_max, j, num,
        ans, k, tmp_sum, l, tmp_min;
    for (i = 0; i != t; ++i) {
        std::cin >> n;
        std::vector<int> inq_db;
        inq_db.reserve(n);
        tmp_max = tmp_gcd = 0;
        for (j = 0; j != n; ++j) {
            std::cin >> num;
            inq_db.emplace_back(num);
            tmp_gcd = std::gcd(tmp_gcd, num);
            tmp_max = std::max(tmp_max, num);
        }
        std::vector<int> buckets(tmp_max + 1);
        for (auto const& elem : inq_db) {
            ++buckets[elem];
        }
        ans = std::numeric_limits<int>::max();
        for (k = tmp_gcd + 1; k <= tmp_max; ++k) {
            tmp_sum = 0;
            for (l = k; l <= tmp_max; l += k) {
                tmp_sum += buckets[l];
            }
            tmp_min = n - tmp_sum;
            if (tmp_min != n && tmp_min < ans) {
                ans = tmp_min;
            }
        }
        std::cout << ans << '\n';
    }
    return 0;
}

我正在计算 x (tmp_gcd) 并在我正在处理的查询 t 中找出 num (tmp_max) 的最大值。我用 max + 1 个零（计数器）初始化桶。我这样做是为了避免每次都使用 1000000 个计数器初始化存储桶。我没有将数字拆分为其 div isors，而是使用桶中的计数器来计算等于其索引的数字。桶中的第 5 个元素计算我在查询中有多少个值为 5 的数字，第 100 个元素 - 值为 100 等等。我从索引 x + 1 开始遍历存储桶，并找出存储桶中有多少个 GCD = k 的数字。这里的idea是数字k、2k、3k、4k、5k等的GCD = k.我找出导致最小移除次数的数字 (ans)。

我的 ideas 的问题是它们在最后 5 个测试用例中超过了时间限制。我需要一些帮助来优化它们，或者如果无法获得新的帮助。提前感谢您的宝贵时间。

@Damien 我这样修改了你的逻辑：

#include <iostream>
#include <map>
#include <vector>
#include <numeric>
#include <cmath>
#include <algorithm>

std::vector<int> split(int num) {
    std::vector<int> ret;
    if ((num & 1) == 0) {
        ret.emplace_back(2);
        do {
            num >>= 1;
        } while ((num & 1) == 0);
    }
    int div, div_lim;
    for (div = 3, div_lim = static_cast<int>(std::sqrt(num)); div <= div_lim; div += 2) {
        if (num % div == 0) {
            ret.emplace_back(div);
            do {
                num /= div;
            } while (num % div == 0);
            div_lim = static_cast<int>(std::sqrt(num));
        }
    }
    if (num != 1) {
        ret.emplace_back(num);
    }
    return ret;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    int i, n, x, j, num, ans;
    std::map<int, int>::const_iterator it;
    for (i = 0; i != t; ++i) {
        std::cin >> n;
        std::vector<int> seq;
        seq.reserve(n);
        x = 0;
        for (j = 0; j != n; ++j) {
            std::cin >> num;
            seq.emplace_back(num);
            x = std::gcd(x, num);
        }
        if (x != 1) {
            for (auto& elem : seq) {
                elem /= x;
            }
        }
        std::map<int, int> lookup;
        for (auto const& elem : seq) {
            auto ret = split(elem);
            for (auto const& div : ret) {
                ++lookup[div];
            }
        }
        it = std::max_element(lookup.cbegin(), lookup.cend(),
            [](std::pair<const int, int> const& lhs, std::pair<const int, int> const& rhs) {
                return lhs.second < rhs.second;
            });
        ans = n - it->second;
        std::cout << ans << '\n';
    }
    return 0;
}

但遗憾的是我在最后 5 个测试用例中遇到了 TLE。

@TonyK 它是保加利亚语的，因为该任务是在保加利亚竞争性编程竞赛中给出的。

如果我有这个 (4 6 8 10 12 14) 测试 GCD 是 2。现在让我们把每个数字分成它的 div 等值：

4 (1, 2, 4)

6 (1, 2, 3, 6)

8 (1, 2, 4, 8)

10 (1, 2, 5, 10)

12 (1, 2, 3, 4, 6, 12)

14 (1, 2, 7, 14)

GCD>2的候选人如下：

14->我必须删除除 14->5 以外的所有数字

12->我必须删除除 12->5 以外的所有数字

10->我必须删除除 10->5 以外的所有数字

8->我必须删除除 8->5 之外的所有数字

7->我必须删除除 14->5 之外的所有数字

6->我必须删除 4、8、10 和 14->4 个删除

5->我必须删除除 10->5 以外的所有数字

4->我必须删除 6、10 和 14->3 个删除

3->我必须删除 4、8、10 和 14->4 个删除

答案是 3 次移除，它们可以在 GCD = 4 时实现。

Answer 1

这是一个相当快速的解决方案。

第一步是计算全局 gcd 并将所有数字除以它。

全局GCD现在等于1。现在的问题是找到最小的移除次数，使得这个GC不再等于1。

为此，我们对每个数字进行素数分解，并找出其中出现次数最多的素数。

结果是数组大小减去这个素数出现的次数。

复杂度主要由质数分解决定：O(n sqrt(m))，其中m为最大数据值

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <limits>
#include <map>
#include <cmath>

//  For test
void print (const std::vector<int> &v) {
        for (auto &x: v) {
                std::cout << x << " ";
        }
        std::cout << std::endl;
}

//  Get the prime factors of a number (multiplicity is not important here)

std::vector<int> get_primes (int n) {
    int n_sav = n;
    if (n <= 1) return {};
    std::vector<int> primes;

    if (n % 2 == 0) {
        primes.push_back(2);
        n /= 2;
        while (n%2 == 0) {n /= 2;}
    }
    int max_prime = sqrt(n);
    int p = 3;
    while (p <= max_prime) {
        if (n % p == 0) {
            primes.push_back(p);
            n/= p;
            while (n%p == 0) {n /= p;}
            max_prime = sqrt(n);
        }
        p += 2;
    }
    if (n != 1) {
        primes.push_back(n);
    }
    //std::cout << n_sav << ": ";
    //print (primes);
    return primes;
}


int min_removals (std::vector<int>& numbers) {
    int n = numbers.size();
    if (n == 1) return -1;
    int current_gcd = numbers[0];
    for (int i = 1; i < n; ++i) current_gcd = std::gcd (current_gcd, numbers[i]);
    std::cout << "current GCD = " << current_gcd << "\n";
    if (current_gcd != 1) {
        for (int i = 0; i < n; ++i) numbers[i] /= current_gcd;
    }
    std::map<int, int> list_primes;
    for (auto x: numbers) {
        auto primes = get_primes(x);
        for (int i: primes) {
            list_primes[i]++;
        }
    }
    int most_frequent = 0;
    for (const auto& p: list_primes) {
        if (p.second > most_frequent) {
            most_frequent = p.second;
        }
    }
    
    return n - most_frequent;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<int> numbers (n);
        for (int i = 0; i < n; ++i) {
            std::cin >> numbers[i];
        }
        auto ans = min_removals (numbers);
        std::cout << ans << "\n";
    }
    return 0;
}

对于以下变体，通过在主函数中加入素数分解，速度略有提高。这避免了一些无用的数据副本。看来收益是不可忽略的。

int min_removals_new (std::vector<int>& numbers) {
    int n = numbers.size();
    if (n == 1) return -1;
    int current_gcd = numbers[0];
    for (int i = 1; (i < n) && (current_gcd > 1); ++i) current_gcd = std::gcd (current_gcd, numbers[i]);
    if (current_gcd != 1) {
        for (int i = 0; i < n; ++i) numbers[i] /= current_gcd;
    }
    std::map<int, int> list_primes;
    
    for (auto x: numbers) {
        if (x == 1) continue;
        if (x % 2 == 0) {
            list_primes[2]++;
            x /= 2;
            while (x%2 == 0) {x /= 2;}
        }
        int max_prime = sqrt(x);
        int p = 3;
        while (p <= max_prime) {
            if (x % p == 0) {
                list_primes[p]++;
                x/= p;
                while (x%p == 0) {x /= p;}
                max_prime = sqrt(x);
            }
            p += 2;
        }
        if (x != 1) {
            list_primes[x]++;
        }
    }
       
    int most_frequent = 0;
    for (const auto& p: list_primes) {
        if (p.second > most_frequent) {
            most_frequent = p.second;
        }
    }
    
    return n - most_frequent;
}

Answer 2

我终于找到了足够快的解决方案（550-600 毫秒）！

#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <algorithm>
#include <memory>
#include <bitset>
#include <unordered_map>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t;
    std::cin >> t;
    int i, n, j, num, lim = 0, max, div, cpy, ans;
    std::vector<int> ns, gcds(t);
    std::vector<std::vector<int>> db(t);
    std::vector<int>::const_iterator it;
    std::pair<decltype(it), decltype(it)> ret;
    for (i = 0; i != t; ++i) {
        std::cin >> n;
        ns.emplace_back(n);
        db[i].reserve(n);
        for (j = 0; j != n; ++j) {
            std::cin >> num;
            db[i].emplace_back(num);
            gcds[i] = std::gcd(gcds[i], num);
            lim = std::max(lim, num);
        }
        if (gcds[i] != 1) {
            for (auto& elem : db[i]) {
                elem /= gcds[i];
            }
        }
        std::sort(db[i].begin(), db[i].end());
    }
    auto primes = std::make_unique<std::bitset<10000000 + 1>>();
    primes->set();
    primes->set(0, false);
    primes->set(1, false);
    for (i = 2; i * i <= lim; ++i) {
        if (primes->test(i)) {
            for (j = i * i; j <= lim; j += i) {
                primes->set(j, false);
            }
        }
    }
    for (i = 0; i != t; ++i) {
        std::unordered_map<int, int> lookup;
        max = 0;
        for (it = db[i].cbegin(); it != db[i].cend(); it = ret.second) {
            ret = std::equal_range(it, db[i].cend(), *it);
            if (primes->test(*it)) {
                lookup[*it] += ret.second - ret.first;
                if (lookup[*it] > max) {
                    max = lookup[*it];
                }
                continue;
            }
            for (div = 2, cpy = *it; div * div <= cpy; ++div) {
                if (cpy % div == 0) {
                    lookup[div] += ret.second - ret.first;
                    if (lookup[div] > max) {
                        max = lookup[div];
                    }
                    do {
                        cpy /= div;
                    } while (cpy % div == 0);
                }
            }
            if (cpy != 1) {
                lookup[cpy] += ret.second - ret.first;
                if (lookup[cpy] > max) {
                    max = lookup[cpy];
                }
            }
        }
        ans = ns[i] - max;
        std::cout << ans << '\n';
    }
    return 0;
}

我阅读了所有 t 个查询并将它们的编号存储在一个包含 t 个向量的大向量中，每个向量由 n 个元素组成。在 db[i] 中读取和存储 nums 时，我将每个 n 存储在向量 ns 中，计算特定查询 gcds[i] 的 gcd 并找出最大 num lim。当我完成阅读阶段时，我 divide 将 db[i] 中的所有 nums 放入 gcds[i] 中，以便从最终计算中排除 gcds[i]。我对 db[i] 进行排序，以避免对其中重复的数字进行质数分解。基于 lim 我找出了 [2; 范围内的所有素数。 lim] 使用我通过 unique_ptr 素数存储在堆上的位集。我使用 unordered_map 查找处理每个查询 db[i]。使用 for 循环和 equal_range 算法，我跳到 db[i] 中的 nums 上，只对重复的第一个进行质数分解。例如，如果我有 7 7 7 7 7 7 7 13 17 19 ... ret.first 将指向第一个 7 而 ret.second 将指向 13。因为 7 已经是质数（我检查这个使用 bitset 素数）我不会将它分解为素数，我会将其计数器递增 ret.second - ret.first 次，并将该计数器与 max 进行比较，max 表示 db[i] 中最频繁的 num 的计数.如果需要，我会通过分配更新 max。如果 * 它不是质数，我将使用下一个带有 div 和 cpy 的 for 循环对其进行质数分解。如果我遇到像 6 这样的数字，它不能使用第一个 for 循环完全分解，我将在它之后使用 If 子句，因为第一次迭代将找出 2 作为 6 的质因数之一，然后我们将失败3 必须增加其计数器。这就是 if 子句的目的。当我发现哪个是 db[i] 中最频繁的 num 时，我只需从 ns[i] 中减去它的计数，从而找出 ans ，这是为了改进 gcds[i] 必须进行的最少删除次数最多。我输出ans就是这样。

如何最大化 n 个正整数的 GCD，并从代表它们的序列中删除最少数量？

How to maximize the GCD of n positive integers with minimum number of removals from the sequence that represents them?

c++

algorithm

data-structures

number-theory

greatest-common-divisor