codeforces 582A GCD Table

题意简述：

给定一个长度为$n$的序列将这个序列里的数两两求$gcd$得到$n^2$个数

将这$n^2$个数打乱顺序给出求原序列的一种可能的情况

-----------------------------------------------------------------------------------------------------------------------

比赛时一直去想有什么特殊的性质（找规律）比如这些数里为一个数的倍数的数一定是平方个

然而按照这样的思路去想又会有什么分解因式等等最后直接在这一部分就T掉

-----------------------------------------------------------------------------------------------------------------------

比赛结束后$ dwj$ 给了我一份他的$AC$代码发现原来是增量法的运用

我们先假设原序列是非严格递减的

我们把这些数排序后设已经求得原序列前$k$项并且把前$k$项相互之间的$gcd$得到的数全部删掉了

剩下来的最大的那个肯定是原序列中的$k+1$项

然后通过这个数和前$k$项的数$gcd$得到的数我们把它们全部删掉

剩下来的最大的那个肯定是原序列中的$k+2$项

…………

对于删数的操作我们可以用优先队列来维护然后这题就解决了

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

using namespace std;

const int N=;

int a[N*N],ans[N];

int n,len;

priority_queue <int> q;

int main()

{

    scanf("%d",&n);

    int n2=n*n;

    for(int i=;i<=n2;++i)

        scanf("%d",&a[i]);

    sort(a+,a++n2);

    int i=n2;

    while(i)

    {

        if(q.empty()||q.top()!=a[i])

        {

            for(int j=;j<=len;++j)

            {

                q.push(__gcd(ans[j],a[i]));

                q.push(__gcd(ans[j],a[i]));

            }

            printf("%d ",ans[++len]=a[i]);

        }

        else

            q.pop();

        --i;

    }

    return ;

}

巴特西

codeforces 582A GCD Table

最新文章

热门文章