fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;		
  3.  
  4. int ans=1000006;
  5.  
  6. void dfs(int prev,int cur,int cnt, unordered_set <int> &s,vector<vector<int> > &g)
  7. {
  8. 	int i;
  9. 	for(i=0;i<g[cur].size();i++)
  10. 	{
  11. 		if(g[cur][i]!=prev)
  12. 		{
  13. 			if(s.find(g[cur][i])!=s.end())
  14. 			{
  15. 				if(ans>cnt)
  16. 				ans=cnt;
  17. 			}
  18. 			else
  19. 			{
  20. 				s.insert(g[cur][i]);
  21. 				dfs(cur,g[cur][i],cnt+1,s,g);
  22. 			}
  23. 		}
  24. 	}
  25. }
  26.  
  27. int main()
  28. {
  29. 	int i,j,n,x;
  30. 	cin>>n;
  31.  
  32. 	vector<int> a;
  33. 	for(i=0;i<n;i++)
  34. 	{
  35. 		cin>>x;
  36. 		a.push_back(x);
  37. 	}
  38.  
  39. 	for(i=0;i<n;i++)
  40. 	{
  41. 		if(sqrt(a[i])*sqrt(a[i])==n)
  42. 		{
  43. 			cout<<"1";
  44. 			return 0;
  45. 		}
  46. 	}
  47.  
  48.  
  49. 	sort(a.begin(),a.end());
  50.  
  51. 	for(i=1;i<a.size();i++)
  52. 	{
  53. 		if(a[i]==a[i-1])
  54. 		{
  55. 			cout<<"2";
  56. 			return 0;
  57. 		}
  58. 	}
  59.  
  60. 	vector<vector<int> > d;
  61. 	vector<int> h,p;
  62.  
  63. 	for(i=0;i<1000006;i++)
  64. 	{
  65. 		h.push_back(0);
  66. 		p.push_back(0);
  67. 		vector<int> temp;
  68. 		d.push_back(temp);
  69. 	}
  70.  
  71. 	p[1]=0;
  72. 	int c=0;
  73. 	c++;
  74.  
  75. 	for(i=2;i<1000006;i++)
  76. 	{
  77. 		if(h[i]==0)
  78. 		{
  79. 			d[i].push_back(0);
  80. 			p[i]=c;
  81. 			c++;
  82. 			for(j=i;j<1000006;j=j+i)
  83. 			{
  84. 				h[j]=1;
  85. 				if(d[j].size()<4)
  86. 				{
  87. 					d[j].push_back(p[i]);
  88. 				}
  89. 			}
  90. 		}
  91. 	}
  92.  
  93. 	vector<vector<int> > g;
  94.  
  95. 	for(i=0;i<c;i++)
  96. 	{
  97. 		vector<int> temp;
  98. 		g.push_back(temp);
  99. 	}
  100.  
  101. 	for(i=0;i<a.size();i++)
  102. 	{
  103. 		g[d[a[i]][0]].push_back(d[a[i]][1]);
  104. 		g[d[a[i]][1]].push_back(d[a[i]][0]);
  105. 	}
  106.  
  107. 	for(i=0;i<g.size();i++)
  108. 	{
  109. 		if(g[i].size()!=0)
  110. 		{
  111. 			int base=i;
  112. 			int prev=-1;
  113. 			int cur=i;
  114. 			int cnt=1;
  115. 			unordered_set<int> s;
  116. 			s.insert(i);
  117. 			dfs(prev,cur,cnt,s,g);
  118. 		}
  119. 	}
  120.  
  121. 	cout<<ans;
  122. 	return 0;
  123. }
Success #stdin #stdout 0.34s 70592KB
comments (?)
stdin
copy 
3
6 10 15
stdout
copy 
1
https://ideone.com/kzdFz4
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!