fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7gtEMT
language:
C++ (gcc 8.3)
created:
9 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!