HackerRank Number Theory – Divisor Exploration

Challenge: Divisor Exploration

Subdomeniu: Number Theory (number-theory)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464753647

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/divisor-exploration/problem

Cerinta

You are given $D$ datasets where each dataset is in the form of two integers, $m$ and $a$, such that:
$$n = \prod\limits_{i = 1}^{m} p_i^{a+i} \text{, where } p_i \text{ is the } i^{th} \text{ prime.}$$

For each dataset, find and print the following on a new line: 

$$\sum\limits_{d|n} \sigma_{0}(d)$$  

where $\sigma_{0}(x)$ is the count of divisors of $x$. As the answer can be quite large, print the result of this value modulo $(10^9 + 7)$.

Input Format

The first line contains an integer, $D$, denoting the number of datasets. 		
Each line $i$ of the $D$ subsequent lines contains two space-separated integers describing the respective values of $m_i$ and $a_i$ for dataset $i$.

Output Format

For each dataset, print a single integer denoting the result of the summation above modulo $(10^9 + 7)$ on a new line.

Constraints

+ $1 \le D \le 10^5$  
+ $1 \le m \le 10^5$  
+ $0 \le a \le 10^5$

Cod sursa

#!/bin/python3

import sys

MOD = 10 ** 9 + 7
INV2 = (MOD + 1) // 2


def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    d = int(data[0])
    queries = []
    ptr = 1
    max_n = 0
    for _ in range(d):
        m = int(data[ptr])
        a = int(data[ptr + 1])
        ptr += 2
        queries.append((m, a))
        if a + m + 2 > max_n:
            max_n = a + m + 2

    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i - 1] * i % MOD

    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
    for i in range(max_n, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD

    inv2_pow = [1] * (100000 + 5)
    for i in range(1, len(inv2_pow)):
        inv2_pow[i] = inv2_pow[i - 1] * INV2 % MOD

    out = []
    for m, a in queries:
        # Product over i=1..m of ((a+i+1)(a+i+2)/2)
        # = [ (a+2..a+m+1) * (a+3..a+m+2) ] * 2^{-m}
        p1 = fact[a + m + 1] * inv_fact[a + 1] % MOD
        p2 = fact[a + m + 2] * inv_fact[a + 2] % MOD
        ans = p1 * p2 % MOD
        ans = ans * inv2_pow[m] % MOD
        out.append(str(ans))

    sys.stdout.write('\n'.join(out))


if __name__ == '__main__':
    main()