Codeforces Round #628 (Div. 2) 一道过于暴力的 搜索 题。
题目链接:Codeforces 1325E。
系列题解:
1. 「题解」Codeforces Round #628 (Div. 2) A EhAb AnD gCd;
2. 「题解」Codeforces Round #628 (Div. 2) B CopyCopyCopyCopyCopy;
3. 「题解」Codeforces Round #628 (Div. 2) C Ehab and Path-etic MEXs;
4. 「题解」Codeforces Round #628 (Div. 2) D Ehab the Xorcist;
5. 「题解」Codeforces Round #628 (Div. 2) E Ehab’s REAL Number Theory Problem;
6. 「题解」Codeforces Round #628 (Div. 2) F Ehab’s Last Theorem。
题目
原题
题意简述
给一些数,每个的因数个数不超过 $7$,求最少选出多少个,使得乘积为完全平方。无解输出 $-1$。
数据范围
$$1\leq n\leq 10^5$$
$$1\leq a_i\leq10^6$$
时空限制
见原题 pdf
文件。
题解
思路
分解每一个 $a_i$,如果是完全平方或者可以配对的,答案为 $1$ 或 $2$,否则就直接暴搜索答案,答案不可能超过 $10^3$。
代码
#include<bits/stdc++.h> using namespace std; #define reg register #define INF 0X3F3F3F3F #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++) static char buf[100000],*p1=buf,*p2=buf; inline int read(void){ reg bool f=false; reg char ch=getchar(); reg int res=0; while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar(); while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar(); return f?-res:res; } const int MAXN=1000000+5; int n; int a[MAXN]; int ans=INF; vector<pair<int,int>/**/> V[MAXN]; map<pair<int,int>,int> M; void Div(int x,int y){ reg int p=1,q=1; for(int i=2;i*i<=x;++i){ if(x%i==0){ reg int flag=0; while(x%i==0) x=x/i,flag^=1; if(!flag) continue; if(p==1) p=i; else q=i; } } if(x!=1){ if(p==1) p=x; else q=x; } if(p==1&&q==1){ ans=min(ans,1); return; } ++M[make_pair(p,q)]; if(M[make_pair(p,q)]>1){ ans=min(ans,2); return; } V[p].push_back(make_pair(q,y)); V[q].push_back(make_pair(p,y)); return; } bool vis[MAXN]; int dep[MAXN]; queue<int> Q; inline int BFS(int x){ if(V[x].empty()) return INF; memset(vis,false,sizeof(vis)); memset(dep,0,sizeof(dep)); while(!Q.empty())Q.pop(); dep[x]=1,Q.push(x); while(!Q.empty()){ reg int ID=Q.front(); Q.pop(); for(reg int i=0;i<(int)V[ID].size();++i){ if(vis[V[ID][i].second]) continue; if(dep[V[ID][i].first]) return dep[V[ID][i].first]+dep[ID]-1; vis[V[ID][i].second]=true; dep[V[ID][i].first]=dep[ID]+1; Q.push(V[ID][i].first); } } return INF; } int main(void){ n=read(); for(reg int i=1;i<=n;++i){ a[i]=read(); Div(a[i],i); } if(ans!=INF){ printf("%d\n",ans); return 0; } for(reg int i=1;i<=1000;++i) ans=min(ans,BFS(i)); if(ans==INF) puts("-1"); else printf("%d\n",ans); return 0; }
近期评论