Contest Duration: ~ (local time) (100 minutes) Back to Home

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 2018-09-23 22:32:48+0900 D - Factorization taku0728 C++14 (GCC 5.4.1) 400 2235 Byte AC 379 ms 256 KB

#### Judge Result

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