fork download
copy 
  1.  #include<iostream>
  2. #include<cstring>
  3. #include<map>
  4. #include<algorithm>
  5. #include<vector>
  6. using namespace std;
  7. long long dp[500001];
  8. int main()
  9. {
  10. 	long long n, i,m,j,sum,sum1,co;
  11. 	map<long long, long long>v1;
  12. 	vector<long long>v2;
  13. 	dp[1] = 1;
  14. 	memset(dp, -1, sizeof(dp));
  15. 	for (i = 2; i <= 500001; i++)
  16. 	{
  17. 		m = i;
  18. 		v1.clear();
  19. 		co = 0;
  20. 		while (1)
  21. 		{
  22. 			sum1 = 0;
  23. 			for (j = 2; j*j <= m; j++)
  24. 			{
  25. 				if (m%j == 0)
  26. 				{
  27. 					while (m%j == 0)
  28. 					{
  29. 						m = m / j;
  30. 						sum1 = sum1 + j;
  31. 					}
  32. 				}
  33. 			}
  34.  
  35. 			if (m > 1)
  36. 			{
  37. 				sum1 = sum1 + m;
  38.  
  39. 			}
  40. 			if (dp[sum1] != -1)
  41. 			{
  42. 				co = co + dp[sum1];
  43. 				break;
  44. 			}
  45. 			if (v1[sum1] == 0)
  46. 			{
  47. 				co = co + 1;
  48. 				v1[sum1] = 1;
  49. 				m = sum1;
  50. 			}
  51. 			else
  52. 			{
  53.  
  54.  
  55. 				break;
  56. 			}
  57. 		}
  58.  
  59. 		if (sum1!=i)
  60. 			co = co + 1;
  61. 		dp[i] = co;
  62.  
  63. 	}
  64. 	long long k = 0,t;
  65. 	cin >> t;
  66. 	while (t--)
  67. 	{
  68. 		cin >> n >> m;
  69. 		for (i = n; i <= m; i++)
  70. 		{
  71. 			v2.push_back(dp[i]);
  72. 		}
  73. 		sort(v2.begin(), v2.end());
  74. 		cout << "Case " << "#" << ++k << ":\n";
  75. 		cout << v2[v2.size() - 1] << "\n";
  76. 		v2.clear();
  77. 	}
  78. }
Runtime error #stdin #stdout 3.03s 7176KB
comments (?)
stdin
copy 
1
1 1000
stdout
copy 
Standard output is empty
https://ideone.com/IPPlcl
language:
C++14 (gcc 8.3)
created:
8 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!