fork download
  1. #include <iostream>
  2. #include <vector>
  3. #include <stdio.h>
  4. #include <string.h>
  5. #include <map>
  6. #include <fstream>
  7. #include <stdlib.h>
  8. using namespace std;
  9.  
  10. int t, n, m, num;
  11. vector<int> arr;
  12. bool vist[100001][101];
  13. int vis[100001][101], id;
  14. bool f[1101];
  15.  
  16. bool fact(int x) {
  17. int cnt[2] = { }, sum = 0;
  18. while (x % 2 == 0) {
  19. x /= 2;
  20. ++sum;
  21. }
  22. cnt[sum % 2]++;
  23. for (int i = 3; i * i <= x; i += 2) {
  24. sum = 0;
  25. while (x % i == 0) {
  26. x /= i;
  27. ++sum;
  28. }
  29. cnt[sum % 2]++;
  30. }
  31. if (x > 1)
  32. cnt[1]++;
  33. return cnt[0] > cnt[1];
  34. }
  35. bool Ss(int x, int in) {
  36. if (x == 0)
  37. return 1;
  38. if (x < 0 || in < 0)
  39. return 0;
  40. if (vis[x][in] == id)
  41. return vist[x][in];
  42. vis[x][in] = id;
  43. return (vist[x][in] = Ss(x, in - 1) || Ss(x - arr[in], in - 1));
  44. }
  45. int main(int argc, char **argv) {
  46. //freopen("a.in", "r", stdin);
  47. f[0] = f[1] = 0;
  48. for (int i = 2; i <= 1101; ++i)
  49. f[i] = fact(i);
  50. scanf("%d", &t);
  51. while (t--) {
  52. arr.clear();
  53. scanf("%d%d", &n, &m);
  54. for (int i = 0; i < n; ++i) {
  55. scanf("%d", &num);
  56. if (num <= m && f[num])
  57. arr.push_back(num);
  58. }
  59. ++id;
  60. puts(Ss(m, arr.size()) ? "Yes" : "No");
  61. }
  62.  
  63. return 0;
  64. }
  65.  
Success #stdin #stdout 0s 52664KB
stdin
Standard input is empty
stdout
Standard output is empty