Advertisement
Guest User

Untitled

a guest
Sep 23rd, 2019
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. //Make Psycho
  2. //https://www.spoj.com/problems/PSYCHO3/
  3. #include <cstdio>
  4. #include <bitset>
  5. #define MAX 1101
  6. #define KMAX 100001
  7. using namespace std;
  8.  
  9. int gpf[MAX], em[MAX];
  10. int t, n, k;
  11.  
  12. bitset<KMAX> b;
  13.  
  14. int main(){
  15.     //find greatest prime factors
  16.     for(int i = 2; i < MAX; ++i){
  17.         if(gpf[i] != 0) //i is composite, continue
  18.             continue;
  19.         for(int j = i; j < MAX; j += i)
  20.             gpf[j] = i;
  21.     }
  22.     //stores in em[i] the number of even multiplicities minus number of odd
  23.     //multiplicities in the prime factorization of i
  24.     for (int i = 2; i < MAX; i++) {
  25.         //impar = 0 se maior fator primo de i tem expoente par
  26.         int j = i, impar = 0;
  27.         while( j % gpf[i] == 0 ){
  28.             j /= gpf[i];
  29.             impar ^= 1;
  30.         }
  31.         //j eh agora o numero constituido pela fatoração prima de i
  32.         //sem seu maior fator primo
  33.         em[i] = em[j] + (impar ? -1:1);
  34.     }
  35.     scanf("%d", &t);
  36.     while(t--){
  37.         scanf("%d %d", &n, &k);
  38.         b = 1U;
  39.         while(n--){
  40.             int x; scanf("%d", &x);
  41.             if(em[x] > 0) b |= b << x;
  42.         }
  43.         if(b[k]) puts("Yes");
  44.         else puts("No");
  45.     }
  46. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement