5.10 NOI 模拟

最近总是管不住自己摆烂,没法像\(Zwaire\)一样管住自己,摆完之后会有负罪感,一直恶性循环,认识到了这个问题,我希望能逐渐改正(不对,马上放假了,不如摆烂到放假)

话说\(GD,HN\)的老哥都太强了吧,联考根本打不过啊\(QAQ\)

\(T1\)

建图拆点跑匹配都很容易想到,考场上审题不清导致\(RE\)

实际代码可以拿\(20pts\)(枚举质数\(+\)带花树匹配)

//csl1:边上放的一定是最大公因数的约数
//csl2:首先每个因子是互不干扰的,可以单独计算
//枚举质数,把合法的数字提出来
//无解,一个点周围没有任何点
//有解,中间是两个的,两边是一个的
//可以把图分成一条链或者一个环的形式即可 
//反正都要满足,那么随机配一下就好,大胆猜测,存在即合法
//猜测失败,但是可以拆点匹配,不会带花树,随机匹配得搞一下轮数... 
//但是可用的质数是不是有点多?
#include
#define int long long
#define MAXN 1000000
#define MAXM 5005
using namespace std;
int Fin[MAXN+5],a[MAXN+5],PRIID,cnt,n,m;
mapid;
int l,r,zz,NOW,vis1[MAXM],q[MAXM],pre[MAXM],h[MAXM],fa[MAXM],c[MAXM],fl[MAXM];
vectore[MAXM];
int find(int x) { return fa[x]==x?x:fa[x]=find(fa[x]); }
int lca(int u,int v) { for(zz++;fl[u]^zz;swap(u,v)) if(u) fl[u]=zz,u=find(pre[h[u]]); return u; }
void blo(int u,int v,int rt) { for(;find(u)^rt;u=pre[v]) { pre[u]=v,fa[u]=fa[v=h[u]]=rt; if(c[v]&1) c[q[++r]=v]=2; } }
bool bfs(int u) {
    for(iota(fa,fa+1+NOW,0),fill(c,c+1+NOW,0),c[q[l=r=1]=u]=2;l<=r;u=q[++l]) for(int v:e[u]) if(!c[v]) {
        pre[v]=u; c[v]=1; c[q[++r]=h[v]]=2; if(!h[v]) { for(;u;v=u) u=h[pre[v]],h[h[v]=pre[v]]=v; return 1; }
    } else if(c[v]==2) { int l=lca(u,v); blo(u,v,l); blo(v,u,l); } return 0;
}
mappri;
vectorrd[MAXN],ID[MAXN];
map > >Eve;
map,int>RDNUM;
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    for(int i=1,u,v;i<=m;i++)
    {
        scanf("%lld%lld",&u,&v);
//      if(n==10&&i>24)cout<v) swap(u,v);
        RDNUM[make_pair(u,v)]=i;
        Fin[i]=1;
    }
    for(int i=1;i<=n;i++)
    {
        int res=a[i];
        mapHad;
        for(int j=2;j*j<=a[i];j++)
        {
            if(res%j==0)
            {
               while(res%j==0) res/=j,Had[j]++;
            }
        }
        if(res!=1) Had[res]++;
        for(map::iterator it=Had.begin();it!=Had.end();it++)
        {
            if(!id[it->first]) id[it->first]=++PRIID,pri[PRIID]=it->first;
            Eve[id[it->first]].push_back(make_pair(i,it->second));
        }
    }
    if(n>10)return 0;
    for(int i=1;i<=PRIID;i++)
    {
        if(Eve[i].size())
        {
            memset(h,0,sizeof(h));
            int cnt=0;
            mapbc;
            for(int j=0;jy) continue;
                Fin[RDNUM[make_pair(now,y)]]*=pri[i];
            }
            if(cnt!=Ans*2) 
            {
                cout<<-1;
                return 0;
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<