Submission #23885626

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

int64_t* dp[75];
int main() {
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

  int64_t a, b;
  cin >> a >> b;

  const int n = b - a + 1;
  vector<vector<bool>> g(n, vector<bool>(n));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (gcd(a + i, a + j) == 1) {
        g[i][j] = true;
      }
    }
  }

  // TODO: change to sieve
  const int k = 20;
  vector<int> p = { 2,  3,  5,  7, 11, 13, 17, 19, 23, 29,
                   31, 37, 41, 43, 47, 53, 59, 61, 67, 71};

  vector<int> pd(n);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < k; ++j) {
      if ((a + i) % p[j] == 0) {
        pd[i] |= 1 << j;
      }
    }
  }
  dp[0] = new int64_t[1 << 20];
  memset(dp[0], 0, 1 << 23);
  dp[0][0] = 1;

  for (int i = 0; i < n; ++i) {
    dp[i + 1] = new int64_t[1 << 20];
    memset(dp[i + 1], 0, 1 << 23);
    for (int prime_mask = 0; prime_mask < (1 << k); ++prime_mask) {
      // take
      if (!(prime_mask & pd[i])) {
        dp[i + 1][prime_mask | pd[i]] += dp[i][prime_mask];
      }
      // skip
      dp[i + 1][prime_mask] += dp[i][prime_mask];
    }
    delete(dp[i]);
  }

  cout << accumulate(dp[n], dp[n] + (1 << k), int64_t(0)) << "\n";

  return 0;
}

Submission Info

Submission Time
Task F - Coprime Present
User MrDindows
Language C++ (GCC 9.2.1)
Score 600
Code Size 1307 Byte
Status AC
Exec Time 170 ms
Memory 19976 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All hand_01.txt, hand_02.txt, hand_03.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
hand_01.txt AC 159 ms 19788 KiB
hand_02.txt AC 170 ms 19904 KiB
hand_03.txt AC 163 ms 19968 KiB
random_01.txt AC 41 ms 19904 KiB
random_02.txt AC 128 ms 19912 KiB
random_03.txt AC 158 ms 19920 KiB
random_04.txt AC 94 ms 19964 KiB
random_05.txt AC 120 ms 19972 KiB
random_06.txt AC 159 ms 19976 KiB
random_07.txt AC 59 ms 19848 KiB
random_08.txt AC 98 ms 19912 KiB
random_09.txt AC 161 ms 19964 KiB
random_10.txt AC 94 ms 19900 KiB
random_11.txt AC 134 ms 19904 KiB
random_12.txt AC 160 ms 19788 KiB
random_13.txt AC 52 ms 19852 KiB
random_14.txt AC 97 ms 19892 KiB
random_15.txt AC 164 ms 19840 KiB
random_16.txt AC 51 ms 19836 KiB
random_17.txt AC 121 ms 19844 KiB
random_18.txt AC 153 ms 19964 KiB
random_19.txt AC 87 ms 19896 KiB
random_20.txt AC 143 ms 19960 KiB
random_21.txt AC 153 ms 19848 KiB
random_22.txt AC 87 ms 19972 KiB
random_23.txt AC 137 ms 19856 KiB
random_24.txt AC 165 ms 19788 KiB
random_25.txt AC 66 ms 19844 KiB
random_26.txt AC 159 ms 19836 KiB
random_27.txt AC 151 ms 19904 KiB
random_28.txt AC 80 ms 19896 KiB
random_29.txt AC 127 ms 19904 KiB
random_30.txt AC 159 ms 19868 KiB
sample_01.txt AC 31 ms 19836 KiB
sample_02.txt AC 25 ms 19544 KiB
sample_03.txt AC 123 ms 19832 KiB