Submission #25210840

Source Code Expand

#include <iostream>
using namespace std;

int N, M;
int A[100005];

// Numeric {{{
#include <vector>
#include <map>
#include <set>
class Numeric {
public:
  template<typename T>
  static T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
  template<typename T>
  static T lcm(T a, T b) { return a / gcd(a, b) * b; }
  static bool is_prime(int n, int MaxN = 3000000) {
    static std::vector<bool> p(MaxN+2, false);
    if (p[MaxN+1]) { return p[n]; }
    p[MaxN+1] = true;

    for (int i = 0; i <= MaxN; i++) { p[i] = 1; }
    p[0] = p[1] = 0;
    p[2] = 1;
    for (int i = 2; i <= MaxN; i++) {
      if (p[i]) {
        for (int j = i*2; j <= MaxN; j+=i) {
          p[j] = 0;
        }
      }
    }
    return p[n];
  }
  static bool is_prime_naive(long long n) {
    if (n <= 1) { return false; }
    for (long long i = 2; i*i <= n; i++) {
      if(n%i == 0) { return false; }
    }
    return true;
  }
  static std::vector<int> primes(int n) {
    std::vector<int> res;
    for (int i = 2; i <= n; i++) {
      if (Numeric::is_prime(i)) { res.push_back(i); }
    }
    return res;
  }
  static std::vector<int> factors_flat(int n, bool reverse = true) {
    static std::map<int, std::vector<int> > table;
    if (table.count(n) > 0) { return table[n]; }

    for (int i = 2; i*i <= n; i++) {
      if (n % i == 0) {
        std::vector<int> v = factors_flat(n/i, false);
        v.push_back(i);
        if (reverse) {
          for (int j = 0; j < v.size()/2; j++) {
            int k = v[j];
            v[j] = v[v.size()-1-j];
            v[v.size()-1-j] = k;
          }
        }
        return v;
      }
    }
    std::vector<int> v;
    v.push_back(n);
    return table[n] = v;
  }
  static std::vector<std::pair<int, int> > factors(int n) {
    static std::map<int, std::vector<std::pair<int, int> > > table;
    if (table.count(n) > 0) { return table[n]; }

    std::vector<std::pair<int, int> > v;
    for (int i = 2; i*i <= n; i++) {
      if (n % i == 0) {
        bool flag = false;
        for (size_t j = 0; j < v.size(); j++) {
          if (v[j].first == i) {
            v[j].second++;
            flag = true;
            break;
          }
        }
        if (!flag) { v.push_back(std::make_pair(i, 1)); }
        std::vector<std::pair<int, int> > u = Numeric::factors(n / i);
        for (int j = 0; j < u.size(); j++) {
          bool t = false;
          for (int k = 0; k < v.size(); k++) {
            if (v[k].first == u[j].first) {
              v[k].second += u[j].second;
              t = true;
              break;
            }
          }
          if (!t) { v.push_back(u[j]); }
        }
        return table[n] = v;
      }
    }
    if (v.size() > 0 && v[v.size()-1].first == n) {
      v[v.size()-1].second++;
    } else {
      v.push_back(std::make_pair(n, 1));
    }
    return table[n] = v;
  }
  static std::vector<long long> factors_naive_flat(long long n) {
    std::vector<long long> v;
    for (long long i = 2; i*i <= n; i++) {
      if (n % i == 0) {
        v.push_back(i);
        n /= i;
        i--;
      }
    }
    if (n != 1) {
      v.push_back(n);
    }
    return v;
  }
  static std::vector<std::pair<long long, int> > factors_naive(long long n, bool initialize = true) {
    static std::vector<std::pair<long long, int> > v = std::vector<std::pair<long long, int> >();
    if (initialize) { v.clear(); }
    for (long long i = 2; i*i <= n; i++) {
      if (n % i == 0) {
        bool flag = false;
        for (size_t j = 0; j < v.size(); j++) {
          if (v[j].first == i) {
            v[j].second++;
            flag = true;
          }
        }
        if (!flag) { v.push_back(std::make_pair(i, 1)); }
        return Numeric::factors_naive(n / i, false);
      }
    }
    if (v.size() > 0 && v[v.size()-1].first == n) {
      v[v.size()-1].second++;
    } else {
      v.push_back(std::make_pair(n, 1));
    }
    return v;
  }
};
void NumericSample() {
  printf("============ NumericSample ============\n");
  printf("%d\n", Numeric::gcd(234, 345));
  printf("%d\n", Numeric::lcm(234, 345));
  printf("%d\n", Numeric::is_prime(1007));
  printf("%d\n", Numeric::is_prime(10007));
  printf("%d\n", Numeric::is_prime_naive(1000000000000037LL));

  std::vector<int> primes = Numeric::primes(31);
  for (size_t i = 0; i < primes.size(); i++) { printf("%d ", primes[i]); } puts("");

  std::vector<std::pair<int, int> > factors1 = Numeric::factors(123456);
  for (size_t i = 0; i < factors1.size(); i++) { printf("(%d, %d) ", factors1[i].first, factors1[i].second); } puts("");

  std::vector<int> factors_flat1 = Numeric::factors_flat(123456);
  for (size_t i = 0; i < factors_flat1.size(); i++) { printf("%d ", factors_flat1[i]); } puts("");

  std::vector<std::pair<int, int> > factors2 = Numeric::factors(32);
  for (size_t i = 0; i < factors2.size(); i++) { printf("(%d, %d) ", factors2[i].first, factors2[i].second); } puts("");

  std::vector<int> factors_flat2 = Numeric::factors_flat(32);
  for (size_t i = 0; i < factors_flat2.size(); i++) { printf("%d ", factors_flat2[i]); } puts("");

  std::vector<std::pair<long long, int> > factors_naive = Numeric::factors_naive(972439611840LL);
  for (size_t i = 0; i < factors_naive.size(); i++) { printf("(%lld, %d) ", factors_naive[i].first, factors_naive[i].second); } puts("");

  std::vector<long long> factors_naive_flat = Numeric::factors_naive_flat(972439611840LL);
  for (size_t i = 0; i < factors_naive_flat.size(); i++) { printf("%lld ", factors_naive_flat[i]); } puts("");
}
// }}} Numeric

bool T[100005];

int main() {
  cin >> N >> M;
  for (int i = 0; i < N; i++) { cin >> A[i]; }

  set<int> s;
  for (int i = 0; i < N; i++) {
    if (A[i] == 1) { continue; }
    vector<int> fs = Numeric::factors_flat(A[i]);
    for (int j = 0; j < fs.size(); j++) {
      s.insert(fs[j]);
    }
  }
  for (int i : s) {
    for (int j = i; j <= M; j+=i) {
      T[j] = 1;
    }
  }
  vector<int> ans;
  for (int i = 1; i <= M; i++) {
    if (!T[i]) { ans.push_back(i); }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << endl;
  }
}

Submission Info

Submission Time
Task D - Coprime 2
User daimatz
Language C++ (GCC 9.2.1)
Score 400
Code Size 6319 Byte
Status AC
Exec Time 182 ms
Memory 5500 KiB

Compile Error

./Main.cpp: In static member function ‘static std::vector<int> Numeric::factors_flat(int, bool)’:
./Main.cpp:57:29: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   57 |           for (int j = 0; j < v.size()/2; j++) {
      |                           ~~^~~~~~~~~~~~
./Main.cpp: In static member function ‘static std::vector<std::pair<int, int> > Numeric::factors(int)’:
./Main.cpp:87:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   87 |         for (int j = 0; j < u.size(); j++) {
      |                         ~~^~~~~~~~~~
./Main.cpp:89:29: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   89 |           for (int k = 0; k < v.size(); k++) {
      |                           ~~^~~~~~~~~~
./Main.cpp: In function ‘int main()’:
./Main.cpp:187:23: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  187 |     for (int j = 0; j < fs.size(); j++) {
      |                     ~~^~~~~~~~~~~
./Main.cpp:201:21: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  201 |   for (int i = 0; i < ans.size(); i++) {
      |                   ~~^~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 1
AC × 29
Set Name Test Cases
Sample sample_01.txt
All sample_01.txt, special_01.txt, special_02.txt, special_03.txt, special_04.txt, special_05.txt, special_06.txt, special_07.txt, special_08.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt
Case Name Status Exec Time Memory
sample_01.txt AC 8 ms 3604 KiB
special_01.txt AC 107 ms 5500 KiB
special_02.txt AC 104 ms 5452 KiB
special_03.txt AC 103 ms 5340 KiB
special_04.txt AC 107 ms 5472 KiB
special_05.txt AC 176 ms 4304 KiB
special_06.txt AC 182 ms 4152 KiB
special_07.txt AC 96 ms 4316 KiB
special_08.txt AC 87 ms 5352 KiB
test_01.txt AC 2 ms 3628 KiB
test_02.txt AC 53 ms 4536 KiB
test_03.txt AC 54 ms 4648 KiB
test_04.txt AC 54 ms 4592 KiB
test_05.txt AC 99 ms 5160 KiB
test_06.txt AC 43 ms 4548 KiB
test_07.txt AC 77 ms 4992 KiB
test_08.txt AC 169 ms 4056 KiB
test_09.txt AC 81 ms 4180 KiB
test_10.txt AC 109 ms 4908 KiB
test_11.txt AC 116 ms 4072 KiB
test_12.txt AC 106 ms 5180 KiB
test_13.txt AC 108 ms 5216 KiB
test_14.txt AC 107 ms 5128 KiB
test_15.txt AC 153 ms 3816 KiB
test_16.txt AC 64 ms 3716 KiB
test_17.txt AC 42 ms 3876 KiB
test_18.txt AC 36 ms 3740 KiB
test_19.txt AC 31 ms 3732 KiB
test_20.txt AC 27 ms 3740 KiB