fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <vector>
  7. #include <set>
  8. #include <map>
  9. #include <unordered_set>
  10. #include <unordered_map>
  11. #include <queue>
  12. #include <ctime>
  13. #include <cassert>
  14. #include <complex>
  15. #include <string>
  16. #include <cstring>
  17. #include <chrono>
  18. #include <random>
  19. #include <queue>
  20. #include <bitset>
  21. using namespace std;
  22.  
  23. #ifdef LOCAL
  24. 	#define eprintf(...) fprintf(stderr, __VA_ARGS__)
  25. #else
  26. 	#define eprintf(...) 42
  27. #endif
  28.  
  29. typedef long long ll;
  30. typedef pair<int, int> pii;
  31. typedef pair<ll, int> pli;
  32. typedef pair<ll, ll> pll;
  33. typedef long double ld;
  34. #define mp make_pair
  35. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  36.  
  37. ll gcd(ll x, ll y) {
  38. 	return y == 0 ? x : gcd(y, x % y);
  39. }
  40.  
  41. const ll INF = (ll)1e16;
  42.  
  43. const int N = (int)1e6 + 55;
  44. const int K = 11;
  45. const int M = (1 << K) + 5;
  46. int n;
  47. pll a[N];
  48. ll e[K];
  49. ll d[M];
  50. int m;
  51. ll p[K];
  52. ll r[N];
  53. vector<pli> c[N];
  54. int ID;
  55. ll dp[K + 1][M];
  56. pli trans[M][K];
  57. vector<int> trans2[N];
  58. ll k;
  59.  
  60. void addTrans(int mask, pli w) {
  61. 	for (int i = 0; i < m; i++) {
  62. 		if (w < trans[mask][i])
  63. 			swap(w, trans[mask][i]);
  64. 	}
  65. }
  66.  
  67. int main()
  68. {
  69. //	freopen("input.txt", "r", stdin);
  70. //	freopen("output.txt", "w", stdout);
  71.  
  72. 	scanf("%d%lld", &n, &k);
  73. 	ll X = 0;
  74. 	for (int i = 0; i < n; i++) {
  75. 		scanf("%lld", &a[i].first);
  76. 		X = gcd(X, a[i].first);
  77. 	}
  78. 	for (int i = 0; i < n; i++)
  79. 		scanf("%lld", &a[i].second);
  80. 	for (ll x = 2; x * x <= X; x++) {
  81. 		if (X % x) continue;
  82. 		p[m++] = x;
  83. 		while(X % x == 0) X /= x;
  84. 	}
  85. 	if (X > 1) {
  86. 		p[m++] = X;
  87. 	}
  88. /*
  89. 	cerr << m << endl;
  90. 	for (int i = 0; i < m; i++)
  91. 		cerr << p[i] << " ";
  92. 	cerr << endl;
  93. */
  94. 	for (int mask = 0; mask < (1 << m); mask++)
  95. 		for (int i = 0; i <= m; i++)
  96. 			dp[i][mask] = INF;
  97. 	dp[0][0] = 0;
  98.  
  99. 	for (int i = 0; i < n; i++) {
  100. 		ll x = a[i].first, y = 1;
  101. 		for (int j = 0; j < m; j++) {
  102. 			while(x % p[j] == 0) {
  103. 				x /= p[j];
  104. 				y *= p[j];
  105. 			}
  106. 		}
  107. 		a[i].first = y;
  108. 	}
  109.  
  110. 	sort(a, a + n);
  111. 	ID = -1;
  112. 	for (int i = 0; i < n; i++) {
  113. 		if (i == 0 || a[i].first != a[i - 1].first) {
  114. 			ID++;
  115. 			r[ID] = a[i].first;
  116. 		}
  117. 		c[ID].push_back(mp(a[i].second, i));
  118. 	}
  119. 	ID++;
  120.  
  121. 	for (int mask = 0; mask < (1 << m); mask++)
  122. 		for (int i = 0; i < m; i++)
  123. 			trans[mask][i] = mp(INF, -1);
  124.  
  125. 	for (int it = 0; it < ID; it++) {
  126. 		while((int)c[it].size() > m) c[it].pop_back();
  127. 		ll x = r[it];
  128. 		for (int i = 0; i < m; i++) {
  129. 			e[i] = 1;
  130. 			while(x % p[i] == 0) {
  131. 				e[i] *= p[i];
  132. 				x /= p[i];
  133. 			}
  134. 		}
  135. 		d[0] = 1;
  136. 		for (int mask = 1; mask < (1 << m); mask++) {
  137. 			int pos = 0;
  138. 			while(((mask >> pos) & 1) == 0) pos++;
  139. 			d[mask] = d[mask ^ (1 << pos)] * e[pos];
  140. 			if (d[mask] <= k) {
  141. 				for (int i = 0; i < (int)c[it].size(); i++) {
  142. 					addTrans(mask, c[it][i]);
  143. 				}
  144. 			}
  145. 		}
  146. 	}
  147.  
  148. 	for (int mask = 0; mask < (1 << m); mask++)
  149. 		for (int i = 0; i < m; i++)
  150. 			if (trans[mask][i].second != -1) {
  151. //				cerr << mask << " " << trans[mask][i].first << endl;
  152. 				trans2[trans[mask][i].second].push_back(mask);
  153. 			}
  154.  
  155. 	for (int i = 0; i < n; i++) {
  156. 		if (trans2[i].empty()) continue;
  157. 		for (int s = m; s > 0; s--)
  158. 			for (int nmask : trans2[i]) {
  159. 				int all = (1 << m) - 1 - nmask;
  160. 				for (int mask = all;; mask = (mask - 1) & all) {
  161. 					dp[s][mask ^ nmask] = min(dp[s][mask ^ nmask], dp[s - 1][mask] + a[i].second);
  162. 					if (mask == 0) break;
  163. 				}
  164. 			}
  165. 	}
  166.  
  167. 	ll ans = INF;
  168. 	for (int i = 0; i <= m; i++)
  169. 		if (dp[i][(1 << m) - 1] < INF)
  170. 			ans = min(ans, i * dp[i][(1 << m) - 1]);
  171. 	if (ans == INF)
  172. 		printf("-1\n");
  173. 	else
  174. 		printf("%lld\n", ans);
  175.  
  176. 	return 0;
  177. }
  178.  
Success #stdin #stdout 0.01s 86144KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/FISOEZ
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!