fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool f[1101], prime[1101];
  5. int arr[101], ln, n, m, t;
  6. vector<int> p;
  7. void siv() {
  8. 	prime[0] = prime[1] = 1;
  9. 	int n = sqrt(1100);
  10. 	for (int i = 4; i <= n; i += 2)
  11. 		prime[i] = 1;
  12.  
  13. 	for (int i = 3; i * i <= n; i += 2) {
  14. 		if (!prime[i])
  15. 			for (int j = i * i; j <= n; j += i)
  16. 				prime[j] = 1;
  17. 	}
  18. 	p.push_back(2);
  19. 	for (int i = 3; i <= n; i += 2)
  20. 		if (!prime[i])
  21. 			p.push_back(i);
  22. }
  23. inline bool fact(int x) {
  24. 	int cnt[2] = { }, sum = 0;
  25. 	for (int i = 0, ln = p.size(); i < ln && p[i] * p[i] <= x; ++i) {
  26. 		for (sum = 0; x % p[i] == 0; ++sum, x /= p[i])
  27. 			;
  28. 		cnt[sum % 2]++;
  29. 	}
  30. 	if (x > 1)
  31. 		cnt[1]++;
  32. 	return cnt[0] > cnt[1];
  33. }
  34. bool dp[100001][101] = { };
  35.  
  36. int Ss() {
  37. 	for (int i = 0; i < ln; ++i)
  38. 		dp[0][i] = 1;
  39. 	for (int i = 1; i <= m; ++i) {
  40. 		for (int j = 1; j <= ln; ++j) {
  41. 			dp[i][j] = dp[i][j - 1];
  42. 			if (i >= arr[j - 1])
  43. 				dp[i][j] = dp[i][j] || dp[i - arr[j - 1]][j - 1];
  44. 		}
  45. 	}
  46. 	return dp[m][ln];
  47. }
  48. int main() {
  49. 	//freopen("a.in","r",stdin);
  50. 	siv();
  51. 	f[0] = f[1] = 0;
  52. 	for (int i = 2; i <= 1101; ++i)
  53. 		f[i] = fact(i);
  54. 	int num;
  55. 	scanf("%d", &t);
  56. 	while (t--) {
  57. 		ln = 0;
  58. 		scanf("%d%d", &n, &m);
  59. 		for (int i = 0; i < n; ++i) {
  60. 			scanf("%d", &num);
  61. 			if (num <= m && f[num])
  62. 				arr[ln++] = num;
  63. 		}
  64. 		puts(Ss() ? "Yes" : "No");
  65. 	}
  66.  
  67. }
  68.  
Success #stdin #stdout 0s 13296KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/9642qf
language:
C++ (gcc 8.3)
created:
10 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!