Submission #3260408


Source Code Expand

Copy
#include <cstdio>

const int MOD = 1e9 + 7, MAX_N = 2e5 + 5;
typedef long long LL;

LL factorial[MAX_N];
LL inverse_factorial[MAX_N];

LL power_mod(LL x, LL power, LL MOD)
{
    LL answer = 1;

    while(power)
    {
        if(power%2 == 1)
            answer = (answer*x)%MOD;

        x = (x*x)%MOD;
        power = power >> 1;
    }

    return answer;
}

LL choose(LL n, LL r, LL MOD)
{
    LL numerator = factorial[n];
    LL denominator_inverse = (inverse_factorial[r]*inverse_factorial[n - r])%MOD;

    return (numerator*denominator_inverse)%MOD;
}

int main()
{
    const int MOD = 1e9 + 7;

    factorial[0] = 1;
    for(int i = 1; i < MAX_N; i++)
        factorial[i] = (i*factorial[i - 1])%MOD;

    inverse_factorial[MAX_N - 1] = power_mod(factorial[MAX_N - 1], MOD - 2, MOD);
    for(int i = MAX_N - 2; i >= 0; i--)
        inverse_factorial[i] = ( (i + 1)*inverse_factorial[i + 1] )%MOD;

    int no_of_factors, n;
    scanf("%d %d", &no_of_factors, &n);

    LL answer = 1;
    for(int i = 2; i*i <= n; i++)
    {
        int exponent = 0;

        while(n%i == 0)
        {
            n = n/i;
            exponent++;
        }

        LL no_of_ways_of_placing_this_prime = choose(exponent + no_of_factors - 1, exponent, MOD);
        answer = (answer*no_of_ways_of_placing_this_prime)%MOD;
    }

    if(n > 1)
    {
        int exponent = 1;

        LL no_of_ways_of_placing_this_prime = choose(exponent + no_of_factors - 1, exponent, MOD);
        answer = (answer*no_of_ways_of_placing_this_prime)%MOD;
    }

    printf("%lld\n", answer);
    return 0;
}

Submission Info

Submission Time
Task D - Factorization
User Saikat
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1654 Byte
Status
Exec Time 4 ms
Memory 3328 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:46:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &no_of_factors, &n);
                                       ^

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