Submission #1229762


Source Code Expand

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

#define MOD 1000000007


vector<ll> primes;

void getPrimes() {
  bool isPrime[1001];
  for(int i = 0; i < 1001; i++) isPrime[i] = true;
  isPrime[1] = false;
  for(int i = 2; i < 1001; i++) {
    if(isPrime[i]) {
      primes.push_back(i);
      for(int k = 2; i * k < 1001; k++) {
        isPrime[i * k] = false;
      }
    }
  }
}

vector< pair<ll, ll> > factors(ll x) {
  unordered_map<ll, ll> m;

  for(ll i = 0; primes[i] * primes[i] <= x && i < primes.size(); i++) {
    while(x % primes[i] == 0) {
      m[primes[i]] += 1;
      x /= primes[i];
    }
  }
  if(x > 1) {
    m[x] = 1;
  }


  vector< pair<ll, ll> > ret;
  for(auto i: m) {
    ret.push_back(i);
  }

  sort(ret.begin(), ret.end());

  return ret;
}

int main() {
  ll N;
  cin >> N;
  getPrimes();
  unordered_map<ll, ll> m;

  for(ll i = 2; i <= N; i++) {
    for(auto k: factors(i)) {
      m[k.first] += k.second;
    }
  }

  vector<pair<ll, ll> > v;

  for(auto i: m) {
    v.push_back(i);
  }


  ll ans = 1;
  for(auto i: v) {
    ans = ans * (i.second + 1) % MOD;
  }
  cout << ans << endl;

}

Submission Info

Submission Time
Task C - Factors of Factorial
User kkty
Language C++14 (GCC 5.4.1)
Score 300
Code Size 1217 Byte
Status AC
Exec Time 2 ms
Memory 256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 10
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_certain_01.txt, subtask_1_certain_02.txt, subtask_1_certain_03.txt, subtask_1_certain_04.txt, subtask_1_rand_01.txt, subtask_1_rand_02.txt, subtask_1_rand_03.txt
Case Name Status Exec Time Memory
sample_01.txt AC 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 2 ms 256 KB
subtask_1_certain_01.txt AC 1 ms 256 KB
subtask_1_certain_02.txt AC 1 ms 256 KB
subtask_1_certain_03.txt AC 2 ms 256 KB
subtask_1_certain_04.txt AC 2 ms 256 KB
subtask_1_rand_01.txt AC 1 ms 256 KB
subtask_1_rand_02.txt AC 1 ms 256 KB
subtask_1_rand_03.txt AC 1 ms 256 KB