fork(2) download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cstring>
  4. #include <cmath>
  5. #include <cassert>
  6. #include <vector>
  7. #include <iostream>
  8. using namespace std;
  9.  
  10. const int MAXN = 3000;
  11. const int SQRT_MAXN = 54;
  12. int MOD = 1000000007;
  13.  
  14. vector<int> primes;
  15. int f[MAXN + 1], prime2index[MAXN + 1], dp[2][1 << 16];
  16.  
  17. int main()
  18. {
  19.     // f[i] is the maximum prime factor of i.
  20.     memset(f, -1, sizeof(f));
  21.     memset(prime2index, -1, sizeof(prime2index));
  22.     f[1] = 1;
  23.     for (int i = 2; i <= MAXN; ++ i) {
  24.         if (f[i] == -1) {
  25.             for (int j = i; j <= MAXN; j += i) {
  26.                 f[j] = i;
  27.             }
  28.             prime2index[i] = primes.size();
  29.             primes.push_back(i);
  30.         }
  31.     }
  32.  
  33.     int tests, test = 1;
  34.     for (scanf("%d", &tests); test <= tests; ++ test) {
  35.         int n;
  36.         scanf("%d%d", &n, &MOD);
  37.         int sqrt_n = (int)sqrt(n) + 1;
  38.         int smallPrimes = 0; // the number of primes smaller than or equal to sqrt(n)
  39.         for (int i = 2; i <= sqrt_n; ++ i) {
  40.             if (f[i] == i) {
  41.                 ++ smallPrimes;
  42.             }
  43.         }
  44.         vector<int> odd(smallPrimes, 0);
  45.         vector< vector<int> > special(primes.size(), vector<int>());
  46.         vector<int> specialCnt(primes.size(), 0);
  47.         vector<int> normal;
  48.         for (int i = 0; i < n; ++ i) {
  49.             int affect = 0, value = i + 1;
  50.             //assert(scanf("%d", &value) == 1);
  51.             assert(value >= 1 && value <= n);
  52.             bool valid = true;
  53.             for (int x = value; x > 1; x /= f[x]) {
  54.                 if (f[x] <= sqrt_n) {
  55.                     int id = prime2index[f[x]];
  56.                     assert(id != -1);
  57.  
  58.                     odd[id] ^= 1;
  59.                     if (affect >> id & 1) {
  60.                         valid = false; // we only need to consider the square free numbers
  61.                     }
  62.  
  63.                     affect ^= 1 << id;
  64.                 }
  65.             }
  66.             if (valid) {
  67.                 if (f[value] <= sqrt_n) {
  68.                     normal.push_back(affect);
  69.                 } else {
  70.                     int id = prime2index[f[value]]; // for a value between 1 and n, there is at most ONE prime factor which is larger than sqrt(n)
  71.                     assert(prime2index[f[value]] != -1);
  72.                     special[id].push_back(affect);
  73.                 }
  74.             }
  75.  
  76.             if (f[value] > sqrt_n) {
  77.                 int id = prime2index[f[value]];
  78.                 specialCnt[id] ^= 1;
  79.             }
  80.  
  81.         }
  82.  
  83.         // compute the set of small primes which should be covered by removed numbers.
  84.         int todo = 0;
  85.         for (int i = 0; i < smallPrimes; ++ i) {
  86.             todo ^= odd[i] << i;
  87.         }
  88.  
  89.         memset(dp, 0, sizeof(dp));
  90.         dp[0][todo] = 1;
  91.         int now = 0, old = 1;
  92.         for (int i = 0; i < normal.size(); ++ i) {
  93.             if ((todo & normal[i]) != normal[i]) {
  94.                 continue;
  95.             }
  96.             int item = normal[i];
  97.  
  98.             now = 1 - now;
  99.             old = 1 - old;
  100.             memcpy(dp[now], dp[old], sizeof(dp[old]));
  101.             for (int mask = 0; mask < 1 << smallPrimes; ++ mask) {
  102.                 if ((mask & item) == item) {
  103.                     dp[now][mask ^ item] += dp[old][mask];
  104.                     if (dp[now][mask ^ item] >= MOD) {
  105.                         dp[now][mask ^ item] -= MOD;
  106.                     }
  107.                 }
  108.             }
  109.         }
  110.  
  111.         int counter = 0;
  112.         for (int i = 0; i < special.size(); ++ i) {
  113.             if (specialCnt[i]) {
  114.                 // we must select one number from special[i]
  115.                 ++ counter;
  116.                 now = 1 - now;
  117.                 old = 1 - old;
  118.                 memset(dp[now], 0, sizeof(dp[now]));
  119.                 for (int j = 0; j < special[i].size(); ++ j) {
  120.                     int item = special[i][j];
  121.                     if ((item & todo) != item) {
  122.                         continue;
  123.                     }
  124.                     for (int mask = 0; mask < 1 << smallPrimes; ++ mask) {
  125.                         if ((mask & item) == item) {
  126.                             dp[now][mask ^ item] += dp[old][mask];
  127.                             if (dp[now][mask ^ item] >= MOD) {
  128.                                 dp[now][mask ^ item] -= MOD;
  129.                             }
  130.                         }
  131.                     }
  132.                 }
  133.             }
  134.         }
  135.         printf("%d\n", dp[now][0]);
  136.     }
  137.     return 0;
  138. }
Success #stdin #stdout 0s 3952KB
comments ()
stdin
copy 
2
3
199
stdout
copy 
2
2
https://ideone.com/7quMsb
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
secret

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!