Submission #3820802
Source Code Expand
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) unique(v.begin(), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;
#define MAX_V 1000000
const int MAX_L = 1000001;
const int MAX_SQRT_B = 1000001;
bool is_prime_array[MAX_L];
bool is_prime_small[MAX_SQRT_B];
const int mod = 1e9 + 7;
const int MAX = 200002;
ll fact[MAX], invfact[MAX];
#define MAX_V 1000000
ll mod_pow(ll a, ll n, ll mod) {
ll res = 1;
while(n > 0) {
if(n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
ll mod_inverse(ll a, ll m) {
return mod_pow(a, m - 2, m);
}
ll nCr(ll n, ll r) {
return fact[n] * invfact[r] % mod * invfact[n - r] % mod;
}
void init() {
fact[0] = invfact[0] = 1;
rep(i, 1, MAX) {
fact[i] = (fact[i - 1] * i) % mod;
invfact[i] = mod_inverse(fact[i], mod);
}
}
bool is_prime(int n) {
for(int i = 2; i * i <= n; i++) {
if(n % i == 0) return false;
}
return n != 1;
}
vector<int> divisor(int n) {
vector<int> res;
for(int i = 1; i * i <= n; i++) {
if(n % i == 0) {
res.push_back(i);
if(i != n / i) res.push_back(n / i);
}
}
return res;
}
map<int, int> prime_factor(int n) {
map<int, int> res;
for(int i = 2; i * i <= n; i++) {
while(n % i == 0) {
++res[i];
n /= i;
}
}
if(n != 1) res[n] = 1;
return res;
}
int eratosthenes(int n) {
bool is_prime[n + 1];
memset(is_prime, true, sizeof(is_prime));
// prime[n];
is_prime[0] = is_prime[1] = false;
int ans = 0;
rep(i, 2, n + 1) {
if(is_prime[i]) {
// prime[ans++] = i;
ans++;
for(int j = 2 * i; j <= n; j += i) is_prime[j] = false;
}
}
return ans;
}
// [a, b)の整数に対して篩を行う
ll segment_eratosthenes(ll a, ll b) {
for(int i = 0; (ll)i * i < b; i++) is_prime_small[i] = true;
for(int i = 0; i < b - a; i++) is_prime_array[i] = true;
for(int i = 2; (ll)i * i < b; i++) {
if(is_prime_small[i]) {
for(int j = 2 * i; (ll)j * j < b; j += i) is_prime_small[j] = false; // [2, sqrt(b))の篩
for(ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i) is_prime_array[j - a] = false; // [a, b)の篩
}
}
ll rsl = 0;
rep(i, 0, sqrt(b)) {
if(is_prime_array[i]) rsl++;
}
return rsl;
}
int main(){
cin.tie(0);
ios::sync_with_stdio(false);
init();
int N, M;
cin >> N >> M;
map<int, int> m = prime_factor(M);
ll rsl = 1;
for(map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
(rsl *= nCr(N + it->second - 1, N - 1)) %= mod;
}
cout << rsl << endl;
}
Submission Info
Submission Time |
|
Task |
D - Factorization |
User |
tsutarou10 |
Language |
C++14 (GCC 5.4.1) |
Score |
400 |
Code Size |
3226 Byte |
Status |
AC |
Exec Time |
33 ms |
Memory |
4352 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 |
33 ms |
4352 KB |
0_small_2 |
AC |
33 ms |
4352 KB |
0_small_3 |
AC |
33 ms |
4352 KB |
1_large_1 |
AC |
33 ms |
4352 KB |
1_large_2 |
AC |
33 ms |
4352 KB |
1_large_3 |
AC |
33 ms |
4352 KB |
2_large_1 |
AC |
33 ms |
4352 KB |
2_large_2 |
AC |
33 ms |
4352 KB |
3_prime_1 |
AC |
33 ms |
4352 KB |
3_prime_10 |
AC |
33 ms |
4352 KB |
3_prime_11 |
AC |
33 ms |
4352 KB |
3_prime_12 |
AC |
33 ms |
4352 KB |
3_prime_13 |
AC |
33 ms |
4352 KB |
3_prime_14 |
AC |
33 ms |
4352 KB |
3_prime_15 |
AC |
33 ms |
4352 KB |
3_prime_16 |
AC |
33 ms |
4352 KB |
3_prime_17 |
AC |
33 ms |
4352 KB |
3_prime_18 |
AC |
33 ms |
4352 KB |
3_prime_19 |
AC |
33 ms |
4352 KB |
3_prime_2 |
AC |
33 ms |
4352 KB |
3_prime_20 |
AC |
33 ms |
4352 KB |
3_prime_21 |
AC |
33 ms |
4352 KB |
3_prime_22 |
AC |
33 ms |
4352 KB |
3_prime_3 |
AC |
33 ms |
4352 KB |
3_prime_4 |
AC |
33 ms |
4352 KB |
3_prime_5 |
AC |
33 ms |
4352 KB |
3_prime_6 |
AC |
33 ms |
4352 KB |
3_prime_7 |
AC |
33 ms |
4352 KB |
3_prime_8 |
AC |
33 ms |
4352 KB |
3_prime_9 |
AC |
33 ms |
4352 KB |
4_hand_1 |
AC |
33 ms |
4352 KB |
4_hand_2 |
AC |
33 ms |
4352 KB |
4_hand_3 |
AC |
33 ms |
4352 KB |
sample_01 |
AC |
33 ms |
4352 KB |
sample_02 |
AC |
33 ms |
4352 KB |
sample_03 |
AC |
33 ms |
4352 KB |