Submission #1079772
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
struct Prime {
int max_check;
int max_prime;
int prime_number;
vector<int> primes;
map<int, int> prime_id;
Prime() {};
Prime(int m) {
initialize(m);
};
void initialize(int m) {
sieve(m);
prime_number = (int)primes.size();
max_check = m;
}
void sieve(int m) {
max_prime = 2;
deque<bool> is_prime(m+1, true);
is_prime[0] = is_prime[1] = false;
int i;
for (i = 2; i <= m; ++i) {
if (!is_prime[i]) {
continue;
}
if (i * i > m) {
break;
}
for (int j = i*2; j <= m; j += i) {
is_prime[j] = false;
}
prime_id[i] = (int)primes.size();
primes.push_back(i);
max_prime = i;
}
for (int j = i; j <= m; ++j) {
if (!is_prime[j]) {
continue;
}
prime_id[j] = (int)primes.size();
primes.push_back(j);
max_prime = j;
}
}
map<int, int> prime_factor(ll x) {
map<int, int> ret;
if ((ll)max_check * (ll)max_check < x) {
return ret;
}
for (int i = 0; i < prime_number; ++i) {
while (x % primes[i] == 0) {
x /= primes[i];
ret[primes[i]] += 1;
}
}
if (x != 1) {
ret[x] += 1;
}
return ret;
}
};
int mod = 1e9+7;
ll po(ll k, ll x) {
if (x == 0) {
return 1;
}
if (x == 1) {
return k % mod;
}
ll y = po(k, x/2);
y = y * y % mod;
if (x % 2 == 1) {
y = y * k % mod;
}
return y;
}
int main() {
int n;
scanf("%d", &n);
Prime pr(32);
/*
rep (i, (int)pr.primes.size()) {
printf("%3d : %d\n", i, pr.primes[i]);
}
*/
map<int, int> mps;
FOR (i, 2, n+1) {
auto appends = pr.prime_factor(i);
for (auto append : appends) {
mps[append.first] += append.second;
}
}
/*
debug(pr.max_prime);
auto appends = pr.prime_factor(997);
for (auto append : appends) {
printf("%3d : %d\n", append.first, append.second);
}
*/
ll ans = 1;
for (auto m : mps) {
ans = ans * (m.second + 1) % mod;
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Factors of Factorial |
User |
tspcx |
Language |
C++14 (Clang 3.8.0) |
Score |
300 |
Code Size |
3070 Byte |
Status |
AC |
Exec Time |
3 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
300 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
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 |
3 ms |
256 KB |
sample_02.txt |
AC |
3 ms |
256 KB |
sample_03.txt |
AC |
3 ms |
256 KB |
subtask_1_certain_01.txt |
AC |
3 ms |
256 KB |
subtask_1_certain_02.txt |
AC |
3 ms |
256 KB |
subtask_1_certain_03.txt |
AC |
3 ms |
256 KB |
subtask_1_certain_04.txt |
AC |
3 ms |
256 KB |
subtask_1_rand_01.txt |
AC |
3 ms |
256 KB |
subtask_1_rand_02.txt |
AC |
3 ms |
256 KB |
subtask_1_rand_03.txt |
AC |
3 ms |
256 KB |