Submission #3261324


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long llint;
#define FOR(i, a, b) for(llint i = a; i <= b; ++i)
#define REP(i, n) for(llint i = 0; i < n; ++i)

const llint maxSUM = 111'111;
const llint mod = 1'000'000'007;

llint fact[maxSUM + 1];
llint inv[maxSUM + 1];

void scale(llint &value) {
    value %= mod;
}

llint fastExp(llint a, llint n) {
    if (a == 0) {
        return 0;
    }
    llint res = 1;
    while (n > 0) {
        if (n & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

void preProcess() {
    fact[0] = 1;
    FOR(i, 1, maxSUM) {
        fact[i] = fact[i - 1] * i;
        scale(fact[i]);
        inv[i] = fastExp(fact[i], mod - 2);
        scale(inv[i]);
    }
}

llint combination(llint N, llint K) {
    llint res = inv[K] * inv[N - K];
    scale(res);
    res *= fact[N];
    scale(res);
    return res;

}

llint double_combination(llint sum, llint nTerms) {
    llint N = sum + nTerms - 1; // <= 30 + 10^5 - 1
    llint K = nTerms - 1; // <= 10^5 - 1
    return combination(N, K);
}

void run() {
    llint ans = 1, n, m;

    preProcess();
    cin >> n >> m;

    for (llint p = 2; p * p <= m; ++p) {
        if (m % p == 0) {
            llint deg = 0;
            while (m % p == 0) {
                m /= p;
                deg += 1;
            }
            ans *= double_combination(deg, n);
            scale(ans);
        }
    }

    if (m > 1) {
        ans *= double_combination(1, n);
        scale(ans);
    }

    cout << ans << "\n";
}

static void run_with_stack_size(void (*func)(), size_t stackSize) {
    char *stack, *send;
    stack = (char*) malloc(stackSize);
    send = stack + stackSize - 16;
    send = (char*) ((uintptr_t) send / 16 * 16);
    asm volatile(
    "mov %%rsp, (%0)\n"
    "mov %0, %%rsp\n"
    :
    : "r" (send));
    func();
    asm volatile(
    "mov (%0), %%rsp\n"
    :
    : "r" (send));
    free(stack);
}

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    run_with_stack_size(run, 256*1024*1024);
#ifdef LOCAL
    fclose(stdin);
#endif
    return 0;
}

Submission Info

Submission Time
Task D - Factorization
User duckladydinh
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2255 Byte
Status
Exec Time 16 ms
Memory 2048 KB

Test Cases

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