Counting Arrays (Codeforces 893E)
Tags: Math, combinatorics

You are given two positive integer numbers x and y. An array F is called an y-factorization of x iff the following conditions are met:  There are y elements in F, and all of them are integer numbers;  . You have to count the number of pairwise distinct arrays that are y-factorizations of x. Two arrays A and B are considered different iff there exists at least one index i (1 ≤ i ≤ y) such that Ai ≠ Bi. Since the answer can be very large, print it modulo 109 + 7.

Input: The first line contains one integer q (1 ≤ q ≤ 105) — the number of testcases to solve.Then q lines follow, each containing two integers xi and yi (1 ≤ xi, yi ≤ 106). Each of these lines represents a testcase.

Output: Print q integers. i-th integer has to be equal to the number of yi-factorizations of xi modulo 109 + 7.

Note: In the second testcase of the example there are six y-factorizations:  { - 4,  - 1};  { - 2,  - 2};  { - 1,  - 4};  {1, 4};  {2, 2};  {4, 1}. 

Sample Inputs:
2
6 3
4 2

Sample Outputs:
36
6

Solution (Python):
from array import array
md = 10 ** 9 + 7

def fact_all(N):
    lp = array('Q', [2] * (N + 1))
    pr = array('Q', [2])
    pra = pr.append
    for i in range(3, N + 1, 2):
        if lp[i] == 2:
            lp[i] = i
            pra(i)
        for p in pr:
            ip = i * p
            if p > lp[i] or ip > N:
                break
            lp[ip] = p
    return lp

def cnk(n, k):
    if k > n // 2:
        k = n - k
    ans = 1
    for i in range(n - k + 1, n + 1):
        ans *= i
    for i in range(2, k + 1):
        ans //= i
    ans = ans % md
    return ans

def factor(n, lpa=fact_all(10 ** 6)):
    pws = []
    num_ones = 0
    dv = lpa[n]
    while n > 1 and dv * dv <= n:
        lp = 0
        (c, o) = divmod(n, dv)
        while o == 0:
            lp += 1
            n = c
            (c, o) = divmod(n, dv)
        if lp == 1:
            num_ones += 1
        else:
            pws.append(lp)
        dv = lpa[n]
    if n > 1:
        num_ones += 1
    return (pws, num_ones)

def main():
    q = int(input())
    for __ in range(q):
        (x, y) = input().split()
        (x, y) = (int(x), int(y))
        ans = pow(2, y - 1, md)
        (pws, num_ones) = factor(x)
        for f in pws:
            cm = cnk(f + y - 1, f)
            ans = ans * cm % md
        if num_ones:
            ans = ans * pow(y, num_ones, md) % md
        print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
mod = 10 ** 9 + 7
max_n = 10 ** 6 + 100
(fac, inv) = ([1] * max_n, [1] * max_n)
for i in range(2, max_n):
    fac[i] = fac[i - 1] * i % mod
inv[-1] = pow(fac[-1], mod - 2, mod)
for i in range(max_n - 1, 0, -1):
    inv[i - 1] = inv[i] * i % mod

def get_primes(n: int):
    from itertools import chain
    from array import array
    primes = [2, 3]
    is_prime = array('b', (0, 0, 1, 1, 0, 1, 0)) + array('b', (1, 0, 0, 0, 1, 0)) * ((n - 1) // 6)
    for i in chain.from_iterable((range(5, n + 1, 6), range(7, n + 1, 6))):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * 3, n + 1, i * 2):
                is_prime[j] = 0
    return (is_prime, primes)
(_, primes) = get_primes(10 ** 3)
q = int(sys.stdin.buffer.readline().decode('utf-8'))
ans = [0] * q
for i in range(q):
    (x, y) = map(int, sys.stdin.buffer.readline().decode('utf-8').split())
    pfac = []
    for p in primes:
        if x % p == 0:
            pfac.append(0)
            while x % p == 0:
                pfac[-1] += 1
                x //= p
    if x > 1:
        pfac.append(1)
    res = 1
    for c in pfac:
        res = res * fac[c + y - 1] * inv[y - 1] * inv[c] % mod
    res = res * pow(2, y - 1, mod) % mod
    ans[i] = res
sys.stdout.buffer.write('\n'.join(map(str, ans)).encode('utf-8'))

Solution (Python):
import sys
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import math
mod = 10 ** 9 + 7

def main():
    N = 10 ** 6 + 50
    spf = [-1] * (N + 1)
    for i in range(N + 1):
        spf[i] = i
    for i in range(2, int(math.sqrt(N)) + 1):
        if spf[i] == i:
            for j in range(i * 2, N + 1, i):
                if spf[j] == j:
                    spf[j] = i

    def factorize(n):
        d = {}
        while n != 1:
            p = spf[n]
            if p in d:
                d[p] += 1
            else:
                d[p] = 1
            n //= p
        return d
    N = 10 ** 6 + 1000
    fac = [1] * (N + 1)
    finv = [1] * (N + 1)
    for i in range(N):
        fac[i + 1] = fac[i] * (i + 1) % mod
    finv[-1] = pow(fac[-1], mod - 2, mod)
    for i in reversed(range(N)):
        finv[i] = finv[i + 1] * (i + 1) % mod

    def cmb1(n, r, mod):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return fac[n] * finv[r] * finv[n - r] % mod
    N = 10 ** 6 + 50
    table = [0] * N
    table[0] = 1
    for i in range(1, N):
        table[i] = table[i - 1] * 2
        table[i] %= mod
    q = int(input())
    ANS = [0] * q
    for i in range(q):
        (x, y) = map(int, input().split())
        d = factorize(x)
        ans = 1
        for (k, v) in d.items():
            ans *= cmb1(v + y - 1, y - 1, mod)
            ans %= mod
        ans *= table[y - 1]
        ans %= mod
        ANS[i] = ans
    print(*ANS, sep='\n')
if __name__ == '__main__':
    main()