Kaosar and Sequences #12327
Sign in

Kaosar and Sequences (Editorial)

Problem Author:

AlKaosar Hussain

Prepared by:

AlKaosar Hussain

Edited by:

Hasan Saleh (MathModel)

Solution

Here the first value of the sequence is and last value is and remaining every adjacent

value divide each other and there ratio is a prime number, now let the prime factorization

of

n = p_{1}^{c_{1}} p_{2}^{c_{2}} \dots p_{m}^{c_{m}}

Now the main observation is at each step, you multiply the current number a_i by exactly one prime

p_j and each prime p_j occurs c_j times in since you can multiply by one prime at a time,

each prime exponent must be added one by one so total steps to reach n=\sum c_i . include the starting from

the maximum sequence length = 1+\sum c_i .

Now you have c_i copy of p_i each step in the sequence must pick one prime copy and multiply it

as the order matters, because different orders produce different sequences so the total number of steps excluding the

starting 1=\sum c_i . and the number of distinct sequences =

\frac{(\sum c_i)!}{\prod c_i!}\mod 10^9+7

which is multinomial coefficient and its the answer.

MOD = 10**9 + 7
MAXN = 10000
fact = [1] * (MAXN + 1)
invfact = [1] * (MAXN + 1)
for i in range(2, MAXN + 1):
    fact[i] = fact[i - 1] * i % MOD
invfact[MAXN] = pow(fact[MAXN], MOD - 2, MOD)
for i in range(MAXN, 0, -1):
    invfact[i - 1] = invfact[i] * i % MOD
def prime(n):
    factors = {}
    x = n
    p = 2
    while p * p <= x:
        while x % p == 0:
            factors[p] = factors.get(p, 0) + 1
            x //= p
        p += 1
    if x > 1:
        factors[x] = factors.get(x, 0) + 1
    return factors
def multinomial(exp):
    total = sum(exp)
    if total == 0:
        return -1 
    res = fact[total]
    for e in exp:
        res = res * invfact[e] % MOD
    return total, res
def solve(n):
    factors = prime(n)
    exp = list(factors.values())
    return multinomial(exp)
for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print(1,1)
        continue
    a, b = solve(n)
    print(b % MOD,a+1)
Python