fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty