点击打开codeforces题目链接

分析

给你一个长度为N的数组a[],然后可以生成一个N×N的矩阵,第i行第j个数是gcd(a[i], a[j])。现在给你这个矩阵,让你找出原数组,多解时输出任意解。

分析

今天早上打秃了,半年以前做俩题,现在还是俩,伤心……

看codeforces的官方题解,思路并不难。首先矩阵中最大的数一定是数组中的,把他拿出来后,由于gcd(a, b) <= min(a, b),那么当年矩阵的最大值也一定是数组中的,现在在矩阵中已知元素的gcd,继续找最大值……这样到最后一定是正确的。

下面是官方题解:

Let the answer be a1 ≤ a2 ≤ … ≤ an. We will use the fact that gcd(ai, aj) ≤ amin(i, j).

It is true that gcd(an, an) = an ≥ ai ≥ gcd(ai, aj) for every 1 ≤ i, j ≤ n. That means that an is equal to maximum element in the table. Let set an to maximal element in the table and delete it from table elements set. We’ve deleted gcd(an, an), so the set now contains allgcd(ai, aj), for every 1 ≤ i, j ≤ n and 1 ≤ min(i, j) ≤ n - 1.

By the last two inequalities gcd(ai, aj) ≤ amin(i, j) ≤ an - 1 = gcd(an - 1, an - 1). As soon as set contains gcd(an - 1, an - 1), the maximum element in current element set is equal to an - 1. As far as we already know an, let’s delete the gcd(an - 1, an - 1), gcd(an - 1, an),gcd(an, an - 1) from the element set. Now set contains all the gcd(ai, aj), for every 1 ≤ i, j ≤ n and 1 ≤ min(i, j) ≤ n - 2.

We’re repeating that operation for every k from n - 2 to 1, setting ak to maximum element in the set and deleting the gcd(ak, ak),gcd(ai, ak), gcd(ak, ai) for every k < i ≤ n from the set.

One could prove correctness of this algorithm by mathematical induction. For performing deleting and getting maximum element operations one could use multiset or map structure, so solution has complexity .

C++代码

#include <bits/stdc++.h>
using namespace std;

multiset<int> st;
vector<int> res;

int main() {
    int n; cin >> n;
    for(int i = 0; i < n * n; ++i) {
        int x; cin >> x;
        st.insert(x);
    }
    res.push_back(*--st.end());
    st.erase(--st.end());
    while(!st.empty()) {
        int cur = *--st.end();
        st.erase(--st.end());
        for(auto i : res) {
            int g = __gcd(cur, i);
            st.erase(st.find(g));
            st.erase(st.find(g));
        }
        res.push_back(cur);
    }
    for_each(res.begin(), res.end(), [](const int i) { cout << i << " "; });
    return 0;
}

欢迎留言