Submission #3255585
Source Code Expand
/** * File : D.cpp * Author : Kazune Takahashi * Created : 2018-9-23 21:11:13 * Powered by Visual Studio Code */ #include <iostream> #include <iomanip> // << fixed << setprecision(xxx) #include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ; #include <vector> #include <string> // to_string(nnn) // substr(m, n) // stoi(nnn) #include <complex> #include <tuple> #include <queue> #include <stack> #include <map> // if (M.find(key) != M.end()) { } #include <set> #include <functional> #include <random> // auto rd = bind(uniform_int_distribution<int>(0, 9), mt19937(19920725)); #include <chrono> // std::chrono::system_clock::time_point start_time, end_time; // start = std::chrono::system_clock::now(); // double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count(); #include <cctype> #include <cassert> #include <cmath> #include <cstdio> #include <cstdlib> using namespace std; #define DEBUG 0 // change 0 -> 1 if we need debug. typedef long long ll; // const int dx[4] = {1, 0, -1, 0}; // const int dy[4] = {0, 1, 0, -1}; // const int C = 1e6+10; // const ll M = 1000000007; const int MAX_SIZE = 1000010; // 10000010でもよさそう? bool isprime[MAX_SIZE]; vector<int> prime_num; void init() { fill(isprime, isprime + MAX_SIZE, true); isprime[0] = isprime[1] = false; for (auto i = 2; i < MAX_SIZE; i++) { if (isprime[i]) { prime_num.push_back(i); for (auto j = 2; i * j < MAX_SIZE; j++) { isprime[i * j] = false; } } } } bool prime(long long x) { // 2 \leq x \leq MAX_SIZE^2 if (x < MAX_SIZE) { return isprime[x]; } for (auto e : prime_num) { if (x % e == 0) return false; } return true; } const long long MOD = 1000000007; long long inv[MAX_SIZE]; long long fact[MAX_SIZE]; long long factinv[MAX_SIZE]; void init2() { inv[1] = 1; for (int i = 2; i < MAX_SIZE; i++) { inv[i] = ((MOD - inv[MOD % i]) * (MOD / i)) % MOD; } fact[0] = factinv[0] = 1; for (int i = 1; i < MAX_SIZE; i++) { fact[i] = (i * fact[i - 1]) % MOD; factinv[i] = (inv[i] * factinv[i - 1]) % MOD; } } long long C(int n, int k) { if (n >= 0 && k >= 0 && n - k >= 0) { return ((fact[n] * factinv[k]) % MOD * factinv[n - k]) % MOD; } return 0; } map<ll, ll> X; int main() { init(); init2(); ll N, M; cin >> N >> M; if (prime(M)) { cout << N << endl; } else { for (auto x : prime_num) { while (M % x == 0) { M /= x; if (X.find(x) == X.end()) { X[x] = 1; } else { X[x]++; } } } if (M != 1) { X[M] = 1; } ll ans = 1; for (auto x : X) { // cerr << x.first << ": " << x.second << endl; ll k = x.second; ans *= C(k + N - 1, k); ans %= MOD; } cout << ans << endl; } }
Submission Info
Submission Time | |
---|---|
Task | D - Factorization |
User | kazunetakahashi |
Language | C++14 (GCC 5.4.1) |
Score | 400 |
Code Size | 3071 Byte |
Status | AC |
Exec Time | 46 ms |
Memory | 25080 KB |
Judge Result
Set Name | All | Sample | ||||
---|---|---|---|---|---|---|
Score / Max Score | 400 / 400 | 0 / 0 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
All | 0_small_1, 0_small_2, 0_small_3, 1_large_1, 1_large_2, 1_large_3, 2_large_1, 2_large_2, 3_prime_1, 3_prime_10, 3_prime_11, 3_prime_12, 3_prime_13, 3_prime_14, 3_prime_15, 3_prime_16, 3_prime_17, 3_prime_18, 3_prime_19, 3_prime_2, 3_prime_20, 3_prime_21, 3_prime_22, 3_prime_3, 3_prime_4, 3_prime_5, 3_prime_6, 3_prime_7, 3_prime_8, 3_prime_9, 4_hand_1, 4_hand_2, 4_hand_3, sample_01, sample_02, sample_03 |
Sample | sample_01, sample_02, sample_03 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_small_1 | AC | 45 ms | 25080 KB |
0_small_2 | AC | 45 ms | 25080 KB |
0_small_3 | AC | 45 ms | 25080 KB |
1_large_1 | AC | 45 ms | 25080 KB |
1_large_2 | AC | 45 ms | 25080 KB |
1_large_3 | AC | 45 ms | 25080 KB |
2_large_1 | AC | 45 ms | 25080 KB |
2_large_2 | AC | 45 ms | 25080 KB |
3_prime_1 | AC | 45 ms | 25080 KB |
3_prime_10 | AC | 45 ms | 25080 KB |
3_prime_11 | AC | 45 ms | 25080 KB |
3_prime_12 | AC | 45 ms | 25080 KB |
3_prime_13 | AC | 45 ms | 25080 KB |
3_prime_14 | AC | 45 ms | 25080 KB |
3_prime_15 | AC | 45 ms | 25080 KB |
3_prime_16 | AC | 45 ms | 25080 KB |
3_prime_17 | AC | 45 ms | 25080 KB |
3_prime_18 | AC | 46 ms | 25080 KB |
3_prime_19 | AC | 45 ms | 25080 KB |
3_prime_2 | AC | 45 ms | 25080 KB |
3_prime_20 | AC | 45 ms | 25080 KB |
3_prime_21 | AC | 45 ms | 25080 KB |
3_prime_22 | AC | 45 ms | 25080 KB |
3_prime_3 | AC | 45 ms | 25080 KB |
3_prime_4 | AC | 45 ms | 25080 KB |
3_prime_5 | AC | 45 ms | 25080 KB |
3_prime_6 | AC | 45 ms | 25080 KB |
3_prime_7 | AC | 45 ms | 25080 KB |
3_prime_8 | AC | 45 ms | 25080 KB |
3_prime_9 | AC | 45 ms | 25080 KB |
4_hand_1 | AC | 45 ms | 25080 KB |
4_hand_2 | AC | 45 ms | 25080 KB |
4_hand_3 | AC | 45 ms | 25080 KB |
sample_01 | AC | 45 ms | 25080 KB |
sample_02 | AC | 45 ms | 25080 KB |
sample_03 | AC | 45 ms | 25080 KB |