Submission #3423635

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>

using namespace std;

#define MOD 1000000007L
#define IMOD 1000000005L

void mul(int64_t& n, int64_t m) {
    n = (n * (m % MOD)) % MOD;
}

int64_t pow(int64_t n, int64_t p) {
    if (p == 0) {
        return 1;
    }
    if (p == 1) {
        return n;
    }

    int64_t r = pow(n, p/2);
    if (p % 2 == 0) {
        return r * r % MOD;
    } else {
        return (r * r % MOD) * n % MOD;
    }
}

void divide(int64_t& n, int64_t m) {
    if (n == 0) {
        return;
    }

    mul(n, pow(m, IMOD));
}

void add(int64_t& n, int64_t m) {
    n = (n + m) % MOD;
}

long solve(int32_t n) {
  vector<int> f(n + 1, 0);
  vector<bool> p(n, true);
  p[0] = false;
  p[1] = false;
  
  for (int32_t i = 2; i <= n/2; ++i) {
    if (!p[i]) {
      // not prime
      continue;
    }
    
    f[i] += 1;
    for (int32_t j = i + 1; j <= n; ++j) {
      int d = 0;
      int jj = j;
      while (jj % i == 0) {
        jj /= i;
        ++d;
      }
      f[i] += d;
      if (d > 0) {
        p[j] = false;
      }
    }
  }
  for (int32_t i = n/2 + 1; i <= n; ++i) {
    if (p[i]) {
      f[i] += 1;
    }
  }
  
  long ans = 1;
  for (auto ff : f) {
    mul(ans, ff + 1);
  }
  
  return ans;
}

int main() {
  int n;

  cin >> n;
  cout << solve(n) << endl;

  return 0;
}

Submission Info

Judge Result