/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 5ms 1.16 MiB
#2 Accepted 5ms 1.07 MiB
#3 Accepted 7ms 1.289 MiB
#4 Accepted 28ms 1.188 MiB
#5 Accepted 61ms 2.418 MiB
#6 Accepted 26ms 1.207 MiB
#7 Accepted 36ms 1.359 MiB
#8 Accepted 60ms 1.191 MiB
#9 Accepted 41ms 1.352 MiB
#10 Accepted 13ms 1.191 MiB
#11 Accepted 49ms 1.293 MiB

Code

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
using namespace std;

const int N = 1e6 + 6;
vector<int> primes;
int yo[N / 32];
bool composite(int n, int i) { return (n & (1 << i)); }
int makeit(int n, int i) { return (n | (1 << i)); }
void bitwiseSieve() {
  for (int i = 3; i * i <= N; i += 2) {
    if (!composite(yo[i >> 5], i & 31)) {
      for (int j = i * i; j <= N; j += i * 2) {
        yo[j >> 5] = makeit(yo[j >> 5], j & 31);
      }
    }
  }
  primes.push_back(2);
  for (int i = 3; i <= N; i += 2) {
    if (!composite(yo[i >> 5], i & 31)) {
      primes.push_back(i);
    }
  }
}
bool isprime(int x) {
  if (x == 2) {
    return true;
  }
  if (x < 2 || x % 2 == 0) {
    return false;
  }
  return !composite(yo[x >> 5], x & 31);
}

void solve(int cs) {
  bitwiseSieve();
  map<int, int> cnt;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    if (isprime(x)) {
      cnt[x] += 1;
    } else {
      for (auto &p : primes) {
        if (p * p > x)
          break;
        while (x % p == 0) {
          x /= p;
          cnt[p] += 1;
        }
      }
      if (x > 1) {
        cnt[x] += 1;
      }
    }
  }
  int res = 1;
  const int mod = 1e9 + 7;
  for (auto &[_, cc] : cnt) {
    res = res * 1LL * (cc + 1) % mod;
  }
  cout << res << "\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tc = 1;
  // cin >> tc;
  for (int cs = 1; cs <= tc; cs++) {
    solve(cs);
  }
  return 0;
}

Information

Submit By
Type
Submission
Problem
P1060 Divisor
Language
C++20 (G++ 13.2.0)
Submit At
2024-07-10 13:39:11
Judged At
2024-11-11 03:28:14
Judged By
Score
100
Total Time
61ms
Peak Memory
2.418 MiB