fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. const int INF = 1e6;
  5. vector<long long> inp;
  6. vector<bool> fakeprime(INF+1, true);
  7. vector<int> prime;
  8. void gen_prime()
  9. {
  10. 	fakeprime[0] = fakeprime[1] = false;
  11. 	for(int i =2; i<=INF; i++)
  12. 	{
  13. 		if(fakeprime[i])
  14. 		for(long long j = (long long)i*i; j<=INF; j+=(long long)i) fakeprime[j] = false;
  15. 	}
  16. 	for(int i =2; i<=INF; i++) if(fakeprime[i]) prime.push_back(i);
  17.  
  18.  
  19. }
  20.  
  21. int cnt_primeuoc(long long a)
  22. {
  23. 	int res = 0;
  24. 	for(int  x: prime)
  25. 	{
  26. 		if( (long long)x*x > a) break;
  27. 		if(a % x == 0)
  28. 		{
  29. 			int cnt = 0;
  30. 			while(a % x == 0)
  31. 			{
  32. 				cnt++;
  33. 				a /= x;
  34. 			}
  35. 			res+=cnt;
  36. 		}
  37.  
  38. 	}
  39. 	if(a > 1) res++;
  40. 	return res;
  41. }
  42.  
  43. long long gcd(long long a, long long b)
  44. {
  45. 	if(b == 0 ) return a;
  46. 	return gcd(b, a % b);
  47. }
  48.  
  49. void sub1()
  50. {
  51. 	long long ucln = gcd(inp[1], inp[2]);
  52. 	long long bcnn = (inp[1] * inp[2]) /  ucln;
  53. //	cout << ucln << " " << bcnn << endl;
  54. 	long long tmp1 = cnt_primeuoc(min(inp[1], inp[2])) + cnt_primeuoc(max(inp[1], inp[2]) / ucln);
  55. 	// << cnt_primeuoc(min(inp[1], inp[2]));
  56. 	long long tmp2 = cnt_primeuoc(bcnn / inp[1]) + cnt_primeuoc(bcnn / inp[2]);
  57. 	cout << min(tmp1,tmp2) << " " << 2 << endl;
  58. 	cout << min(tmp1, tmp2) << " " << 1;
  59. }
  60.  
  61. int process(long long a, long long b)
  62. {
  63. 	long long ucln = gcd(a, b);
  64. 	long long bcnn = (a * b) /  ucln;
  65. 	long long tmp1 = cnt_primeuoc(min(a, b)) + cnt_primeuoc(max(a, b) / ucln);
  66. 	// << cnt_primeuoc(min(inp[1], inp[2]));
  67. 	long long tmp2 = cnt_primeuoc(bcnn / a) + cnt_primeuoc(bcnn / b);
  68. 	return min(tmp1,tmp2);
  69. }
  70. void sub2()
  71. {
  72. 	for(int  i =1; i<=n; i++)
  73. 	{
  74. 		pair<int, int> res = {1e9, 1e9};
  75. 		for(int j = 1; j<=n; j++)
  76. 		{
  77. 			if(i == j) continue;
  78. 			if(process(inp[i], inp[j]) < res.first)
  79. 			{
  80. 				res.first = process(inp[i], inp[j]);
  81. 				res.second = j;
  82. 			}
  83. 		}
  84. 		cout << res.first << " " << res.second << '\n';
  85. 	}
  86. }
  87.  
  88.  
  89. int main()
  90. {
  91. 	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  92. 	cin >> n;
  93. 	inp.resize(n+1);
  94. 	for(int i =1; i<=n; i++) cin >> inp[i];
  95. 	gen_prime();
  96. //	sub1();
  97. sub2();
  98. 	return 0;
  99. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
3
6 5 25
stdout
copy 
3 2
1 3
1 2
https://ideone.com/ph76CF
language:
C++14 (gcc 8.3)
created:
7 days 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!