CF582A

Aryper · 2021-08-09 19:30:37 · 个人记录

GCD Table

我一开始想这个表是对称的，所以说公约数出现了偶数次，而中间那条斜线出现了奇数次，于是判一下出现次数奇偶就差不多了。

然后发现这个方案不太可行。。。

把最大的数取出，找它与之前寻找到的数列中的元素的 \gcd ，然后就把这个数出现的次数减 2 ，如果这个数出现的次数没了，我们下一次找到这个数的时候直接跳过即可。

然后开桶记一下次数，用 map，增加了一个 \log 的复杂度。

时间复杂度 O(n^2\log n^2) 。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#define ll long long
using namespace std;

const ll N=1e6;

ll n,cnt,tot,cur;

ll ans[N+5],a[N+5];

map<ll,ll> mp;

ll gcd(ll a,ll b) {
    if(!b) return a;
    return gcd(b,a%b);
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    ll y=10,len=1;
    while(y<=x) {y*=10;len++;}
    while(len--) {y/=10;putchar(x/y+48);x%=y;}
}

int main() {

    n=read();

    for(ll i=1;i<=n*n;i++) {
        a[i]=read();mp[a[i]]++;
    }

    sort(a+1,a+n*n+1);

    cur=n*n;
    while(cur>0) {
        while(!mp[a[cur]]&&cur>0) cur--;
        ans[++tot]=a[cur];
        mp[a[cur]]--;
        for(ll i=1;i<tot;i++) mp[gcd(ans[tot],ans[i])]-=2;
    //  printf("test:cur=%lld\n",cur);
    }

    for(ll i=1;i<=n;i++) {
        write(ans[i]);putchar(' ');
    }

    return 0;
}