Submission #1870807

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <cassert>
#include <map>
#define MAXN 2010
#define MAXM 100010
using namespace std;

struct edge{
	int to,next;
	edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXM<<1];

int n,numn;
int a[MAXN];
bool flag[10010];
int prime[10010],nump;
int g[MAXM],nume;
int d[MAXN][MAXN];
bool tag[MAXM],visit[MAXM],used[MAXM];
map<int,int> Sp;
int c[MAXM],numc;
int maxv[MAXN],totmax,totmax2;

void addEdge(int u,int v){
	e[nume]=edge(v,g[u]);
	g[u]=nume++;
}

int gcd(int x,int y){
	if(!y) return x;
	return gcd(y,x%y);
}

void init(){
	for(int i=2;i<10010;i++){
		if(!flag[i]) prime[++nump]=i;
		for(int j=1;j<=nump && i*prime[j]<10010;j++){
			flag[i*prime[j]]=1;
			if(i%prime[j]==0) break;
		}
	}
}

void pre_gao(int x,int v){
	int v0=v;
	for(int i=1;i<=nump && prime[i]*prime[i]<=v0;i++)
		if(v%prime[i]==0){
			while(v%prime[i]==0) v/=prime[i];
			if(!Sp.count(prime[i])) Sp[prime[i]]=++numn;
			addEdge(x,Sp[prime[i]]);
			addEdge(Sp[prime[i]],x);
		}
	if(v>1){
		if(!Sp.count(v)) Sp[v]=++numn;
		addEdge(x,Sp[v]);
		addEdge(Sp[v],x);
	}
}

void dfs(int x){
	visit[x]=1;
	c[x]=numc;
	if(tag[x] && a[x]<maxv[numc]) maxv[numc]=a[x];
	for(int i=g[x];~i;i=e[i].next)
		if(!used[e[i].to] && !visit[e[i].to]){
			dfs(e[i].to);
		}
}

int gao(int l){
	for(int i=1;i<=numn;i++) visit[i]=0;
	totmax2=totmax=numc=0;
	for(int i=1;i<=n;i++)
		if(!used[i] && !visit[i]){
			maxv[++numc]=1<<30;
			dfs(i);
			if(maxv[numc]>totmax){
				totmax2=totmax;
				totmax=maxv[numc];
			}else if(maxv[numc]>totmax2) totmax2=maxv[numc];
		}
	int minv=1<<30;
	for(int i=1;i<=n;i++)
		if(!used[i] && tag[i] && a[i]<minv){
			if(maxv[c[i]]==totmax && a[i]<totmax2) continue;
			if(maxv[c[i]]!=totmax && a[i]<totmax) continue;
			minv=a[i];
		}
	for(int i=1;i<=n;i++)
		if(!used[i] && tag[i] && a[i]==minv){
			used[i]=1;
			for(int j=1;j<=n;j++)
				if(tag[j] && a[j]>a[i]) 
					tag[j]=0;
			for(int j=1;j<=n;j++)
				if(!used[j] && !tag[j] && d[j][i]!=1)
					tag[j]=1;
			return minv;
		}
	assert(0);
}

int main(){
#ifdef DEBUG
	freopen("E.in","r",stdin);
#endif
	memset(g,-1,sizeof g);
	init();
	scanf("%d",&n);
	numn=n;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		pre_gao(i,a[i]);
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			d[i][j]=gcd(a[i],a[j]);
	for(int i=1;i<=n;i++) tag[i]=1;
	for(int i=1;i<=n;i++) printf("%d ",gao(i));
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:110:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:113:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a+i);
                  ^

Judge Result