fork download
copy 
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <queue>
  4. #include <string>
  5. #include <memory.h>
  6. #include <bitset>
  7. #include <vector>
  8. #include <set>
  9. #include <map>
  10. #include <algorithm>
  11. using namespace std;
  12. typedef long long ll;
  13. const int oo = (int)1e9;
  14. typedef pair<int, int> pii;
  15. typedef pair<ll, ll> pll;
  16. using namespace std;
  17. vector<int> B, A, best, take;
  18. bool on[1001];
  19. int mx = -1;
  20. int n, k;
  21. void calc(int i) {
  22. 	if (i == (int)B.size()) {
  23. 		int c = 0;
  24. 		for (int j = 1; j <= n; ++j)
  25. 			c += on[j];
  26. 		if (c > mx)
  27. 			best = take, mx = c;
  28. 		return;
  29. 	}
  30. 	int x = B[i];
  31. 	for (int j = x; j <= n; j += x)
  32. 		on[j] = !on[j];
  33. 	take.push_back(B[i]);
  34. 	calc(i + 1);
  35. 	take.pop_back();
  36. 	for (int j = x; j <= n; j += x)
  37. 		on[j] = !on[j];
  38. 	calc(i + 1);
  39. }
  40. int main() {
  41. #ifndef ONLINE_JUDGE
  42. 	freopen("input.txt", "r", stdin);
  43. 	//freopen("output.txt", "w", stdout);
  44. #endif
  45. 	int t, T = 0;
  46. 	scanf("%d", &t);
  47. 	while (t--) {
  48. 		A.clear();
  49. 		B.clear();
  50. 		best.clear();
  51. 		take.clear();
  52. 		memset(on, 0, sizeof(on));
  53. 		mx = -1;
  54. 		scanf("%d%d", &n, &k);
  55. 		for (int i = 0; i < k; ++i) {
  56. 			int a;
  57. 			scanf("%d", &a);
  58. 			if (a*a <= n)
  59. 				B.push_back(a);
  60. 			else A.push_back(a);
  61. 		}
  62. 		calc(0);
  63. 		for (int i = 0; i < (int)best.size(); ++i) {
  64. 			int x = best[i];
  65. 			for (int j = x; j <= n; j += x)
  66. 				on[j] = !on[j];
  67. 		}
  68. 		best.clear();
  69. 		for (int i = 0; i < (int)A.size(); ++i) {
  70. 			int x = A[i], o = 0;
  71. 			for (int j = x; j <= n; j += x)
  72. 				o += on[j] ? -1 : 1;
  73. 			if (o>0)
  74. 				best.push_back(x);
  75. 		}
  76. 		for (int i = 0; i < (int)best.size(); ++i) {
  77. 			int x = best[i];
  78. 			for (int j = x; j <= n; j += x)
  79. 				on[j] = !on[j];
  80. 		}
  81. 		int res = 0;
  82. 		for (int i = 1; i <= n; ++i)
  83. 			res += on[i];
  84. 		printf("Case #%d: %d\n", ++T, res);
  85. 	}
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
4
10 2
2 5
21 4
2 3 5 7
100 1
5
100 3
3 19 7
stdout
copy 
Case #1: 5
Case #2: 11
Case #3: 20
Case #4: 42
https://ideone.com/pkXHX9
language:
C++ (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!