Soluție HackerRank pentru Divisor Exploration, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Divisor Exploration
  • Domeniu: Number Theory
  • Limbaj: Python 3

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

Cerință

You are given D datasets where each dataset is in the form of two integers, m and a, such that:
n = prodlimits_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:

∑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 ≤ D ≤ 10^5
+ 1 ≤ m ≤ 10^5
+ 0 ≤ a ≤ 10^5

Cod sursă

#!/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()
HackerRank Number Theory – Divisor Exploration