Submission #3261488


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] = inv[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 khaledkee
Language C++14 (GCC 5.4.1)
Score 400
Code Size 2724 Byte
Status
Exec Time 16 ms
Memory 3968 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 16 ms 2048 KB
0_small_2 16 ms 3968 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 15 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 15 ms 2048 KB
3_prime_12 16 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 15 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 16 ms 2048 KB
3_prime_22 15 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 16 ms 2048 KB
3_prime_9 15 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