Submission #3258610


Source Code Expand

Copy
#include <iostream>
#include <vector>
#include <utility>
#include <numeric>
#include <functional>
#include <stdio.h>
#include <math.h>
#include <string>
#include <algorithm>
#include <deque>
#include <queue>
#include <map>

#define rep(i, m, n) for (int (i)(m); (i)<(n); ++(i))
#define repr(i, m, n) for (int (i)(m - 1); (i)>=(n); --(i))
#define repv(i, v) for (unsigned (i)(0); (i)<(v.size()); ++(i))
#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define sortgi(v) sort(all(v), greater<int>())
#define sortgd(v) sort(all(v), greater<double>())
#define sortgll(v) sort(all(v), greater<ll>())
#define debug(x) cerr << #x << ": " << x << '\n'

using namespace std;
using pii = pair<int, int>;
using pss = pair<string, string>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using ll = long long;
using pllll = pair<ll, ll>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vpii = vector<pii>;
using pqi = priority_queue<int>;
using pqd = priority_queue<double>;
using pqll = priority_queue<ll>;
using pqvi = priority_queue<vi>;
using pqvll = priority_queue<vll>;

vll prime(ll n) {
	vll p;
	map<ll, ll> mp;
	ll i = 2;
	while (n != 1) {
		while (n % i == 0) {
			n /= i;
			++mp[i];
		}
		++i;
	}
	for (auto j = mp.begin(); j != mp.end(); ++j) {
		p.push_back(j->second);
	}
	return p;
}

// モジュラ逆数 //
ll mod_inv(ll a, ll m) {
    ll b(m), u(1), v(0);
    while (b) {
        ll t(a / b);
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    if (u < 0) {
        u += m;
    }
    return u;
}

ll nCm(ll n, ll m, ll mod) {
	ll a = 1;
	m = min(n-m, m);
	rep(i, 0, m) {
		a *= n - i;
		a %= mod;
	}
	rep(i, 1, m + 1) {
		a *= mod_inv(i, mod);
		a %= mod;
	}
	return a;
}

int main() {
	ll N, M;
	cin >> N >> M;
	vll p = prime(M);
	ll a = 1;
	ll mod = 1e9 + 7;
	repv(i, p) {
		// cout << p[i] << endl;
		a *= nCm(p[i] + N - 1, N - 1, mod);
		a %= mod;
	}
	cout << a << endl;
}

Submission Info

Submission Time
Task D - Factorization
User taku0728
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2235 Byte
Status
Exec Time 379 ms
Memory 256 KB

Test Cases

Set Name Score / Max Score Test Cases
All 400 / 400 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 0 / 0 sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
0_small_1 1 ms 256 KB
0_small_2 1 ms 256 KB
0_small_3 1 ms 256 KB
1_large_1 2 ms 256 KB
1_large_2 379 ms 256 KB
1_large_3 1 ms 256 KB
2_large_1 5 ms 256 KB
2_large_2 1 ms 256 KB
3_prime_1 1 ms 256 KB
3_prime_10 1 ms 256 KB
3_prime_11 1 ms 256 KB
3_prime_12 1 ms 256 KB
3_prime_13 1 ms 256 KB
3_prime_14 1 ms 256 KB
3_prime_15 1 ms 256 KB
3_prime_16 1 ms 256 KB
3_prime_17 1 ms 256 KB
3_prime_18 1 ms 256 KB
3_prime_19 1 ms 256 KB
3_prime_2 1 ms 256 KB
3_prime_20 1 ms 256 KB
3_prime_21 1 ms 256 KB
3_prime_22 1 ms 256 KB
3_prime_3 1 ms 256 KB
3_prime_4 1 ms 256 KB
3_prime_5 1 ms 256 KB
3_prime_6 1 ms 256 KB
3_prime_7 1 ms 256 KB
3_prime_8 1 ms 256 KB
3_prime_9 1 ms 256 KB
4_hand_1 1 ms 256 KB
4_hand_2 1 ms 256 KB
4_hand_3 1 ms 256 KB
sample_01 1 ms 256 KB
sample_02 1 ms 256 KB
sample_03 1 ms 256 KB