fork download 
  1. // AddPrimeToN.cpp : アプリケーションのエントリ ポイントを定義します。
  2. //
  3.  
  4. #include <iostream>
  5. #include <cstdint>
  6. #include <vector>
  7. #include <cmath>
  8. #include <algorithm>
  9.  
  10. typedef std::vector<std::int64_t> DType;
  11.  
  12. //エラトステネスの篩型プライムエンカウンター。
  13.  
  14. template<class T = std::size_t>
  15. class PrimeEncounterAnother {
  16. public:
  17. 	typedef std::vector<bool> PrimeSet;
  18. 	typedef T Integer;
  19.  
  20. 	PrimeEncounterAnother() {
  21. 		Clear();
  22. 	}
  23.  
  24. 	bool Clear() {
  25. 		Primes.clear();
  26. 		if (Primes.size() == 0) {
  27. 			Primes.push_back(true);
  28. 			Primes.push_back(true);
  29. 			Searched = 1;
  30. 		}
  31. 		return true;
  32. 	}
  33.  
  34. 	bool Search(const Integer& N) {
  35. 		if (Searched >= N) return false;
  36. 		Integer L = static_cast<Integer>(std::sqrt(N)) + 1;
  37. 		Primes.resize(N + 1);
  38. 		for (Integer i = 0; i < L; i++) {
  39. 			if (Primes[i] == true) continue;
  40. 			for (Integer j = (Searched / i) + 1; i*j <= N; j++) {
  41. 				if (j <= 1)continue;
  42. 				Primes[i*j] = true;
  43. 			}
  44. 		}
  45. 		Searched = N + 1;
  46. 		return true;
  47. 	}
  48. 	Integer IsSearched() {
  49. 		return Searched;
  50. 	}
  51. 	Integer Size() {
  52. 		return Primes.size();
  53. 	}
  54. 	bool operator [](const Integer& Idx) {
  55. 		return !Primes[Idx];
  56. 	}
  57. protected:
  58. 	PrimeSet Primes;
  59. 	Integer Searched;
  60. };
  61.  
  62. bool Rec(DType P, DType D, const std::uint64_t& A, const std::uint64_t& V,const std::uint64_t& LN,DType& R) {
  63. 	if (D.size() > LN) return false;
  64. 	if (A < V)return false;
  65. 	if (A == V) {
  66. 		R = D;
  67. 		return true;
  68. 	}
  69.  
  70. 	for (std::size_t i = 0; i < P.size(); i++) {
  71. 		D.push_back(P[i]);
  72. 		P.erase(P.begin() + i);
  73. 		Rec(P, D, A, V + D.back(), LN, R);
  74. 		P.insert(P.begin() + i,D.back());
  75. 		D.pop_back();
  76. 	}
  77.  
  78. 	return false;
  79. }
  80.  
  81. DType MakeHoge(std::uint64_t N) {
  82. 	PrimeEncounterAnother<std::uint64_t> P;
  83. 	DType D;
  84. 	DType TT;
  85. 	P.Search(N);
  86. 	for (std::uint64_t i = 2; i < P.IsSearched(); i++) {
  87. 		if (P[i] == true)D.push_back(i);
  88. 	}
  89. 	for (std::uint64_t i = 2; i <= D.size(); i++) {
  90. 		for (std::size_t j = 1; j <= (N / i)+1; j++) {
  91. 			TT.push_back(D[i]);
  92. 		}
  93. 	}
  94. 	D = TT;
  95. 	TT.clear();
  96. 	std::vector<std::vector<std::int64_t>> DP(D.size() + 2);
  97. 	for (auto& o : DP) {
  98. 		o.resize(N + 2);
  99. 	}
  100. 	std::vector<std::vector<std::vector<std::int64_t>>> T(D.size() + 2);
  101. 	for (auto& o : T) {
  102. 		o.resize(N + 2);
  103. 	}
  104. //	for (std::size_t j = 0; j < D.size(); j++) DP[D.size()][j] = 0;
  105.  
  106. 	for (std::int64_t i = D.size() - 1; i >= 0; i--) {
  107. 		for (std::int64_t j = 0; j <= N; j++) {
  108. 			if (j < D[i]) {
  109. 				DP[i][j] = DP[i + 1][j];
  110. 				T[i][j] = T[i + 1][j];
  111. 			}
  112. 			else {
  113. 				if (DP[i + 1][j] > DP[i + 1][j - D[i]] + D[i]) {
  114. 					DP[i][j] = DP[i + 1][j];
  115. 					T[i][j] = T[i + 1][j];
  116. 				}
  117. 				else {
  118. 					DP[i][j] = DP[i + 1][j - D[i]] + D[i];
  119. 					T[i + 1][j - D[i]].push_back(D[i]);
  120. 					T[i][j] = T[i + 1][j - D[i]];
  121. 				}
  122. 			}
  123. 		}
  124. 	}
  125. 		std::vector<std::int64_t> R = T[0][N];
  126. 		std::sort(R.begin(), R.end());
  127.  
  128. 		return R;
  129.  
  130. }
  131.  
  132. int main()
  133. {
  134. 	std::uint64_t N=0;
  135. 	auto R=MakeHoge(2018);
  136. 	std::cout << R.size() << ": " ;
  137. 	for (auto& o: R) {
  138. 		N += o;
  139. 	}
  140. 	std::cout << N<< ": " ;
  141. 	for (auto& o : R) {
  142. 		std::cout << o << ',';
  143. 	}
  144. 	std::cout<<std::endl;
  145.  
  146.     return 0;
  147. }
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/RVtf4i
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!