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
AC × 36
AC × 3
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