3522 - Nr Div Huge

Cerința

Se dau N perechi de numere n k. Pentru fiecare pereche să se calculeze numărul de divizori al lui .

Date de intrare

Fișierul de intrare input.txt conține pe prima linie numărul N, iar pe următoarele N linii N perechi de numere n și k separate printr-un spațiu.

Date de ieșire

Fișierul de ieșire output.txt va conține pe linia i, 1 ≤ i ≤ N, numărul D, reprezentând numărul de divizori al lui P, calculat pentru perechea cu numărul i. Pentru că acesta poate fi foarte mare se va afișa modulo 1.000.000.007.

Restricții și precizări

• 1 ≤ N ≤ 15.000

Exemplul 1

input.txt:

2

2 3

4 4

output.txt:

8

20

Explicație:

Pentru prima pereche: P=54, iar 54 are 8 divizori.

Pentru cea de-a doua pereche: P=2560, iar 2560 are 20 divizori

Exemplul 2

input.txt:

999999999

2 3

4 4

Output:

Conditii neideplinite

Rezolvare

def ver(n):
    if not(1<=n<=15000):
        print("Conditii neideplinite")
        exit()

def precalculation():
    global prime, nrp
    prime = []
    nrp = 0
    ciur = [0] * 31630
    
    for i in range(3, 31626, 2):
        if ciur[i] == 0:
            for j in range(i * i, 31626, 2 * i):
                ciur[j] = 1
            prime.append(i)
            nrp += 1

def nrdivkn(N, m):
    P = 1
    p = 0
    
    while N % 2 == 0:
        N //= 2
        p += 1
    
    p = (p * m) % mod
    P = (P * p) % mod
    
    for d in range(nrp):
        if prime[d] * prime[d] > N:
            break
        while N % prime[d] == 0:
            p = 0
            while N % prime[d] == 0:
                p += 1
                N //= prime[d]
            if p:
                p = (p * m) % mod
                p = (p + 1) % mod
                P = (P * p) % mod
    
    if N > 1:
        p = 1
        p = (p * m) % mod
        p = (p + 1) % mod
        P = (P * p) % mod
    
    return P

def nrdivk1(N):
    P = 1
    p = 0
    d = 0
    
    while N % 2 == 0:
        N //= 2
        p += 1
    
    p += 1
    P = (P * p) % mod
    
    for d in range(nrp):
        if prime[d] * prime[d] > N:
            break
        p = 0
        while N % prime[d] == 0:
            p += 1
            N //= prime[d]
        if p:
            p = (p + 1) % mod
            P = (P * p) % mod
    
    if N > 1:
        P = (P * 2) % mod
    
    return P

def nrdivkn_2(N, m):
    P = 1
    p = 0
    
    while N % 2 == 0:
        N //= 2
        p += 1
    
    p = (p * m) % mod
    p = (p + 1) % mod
    P = (P * p) % mod
    
    for d in range(nrp):
        if prime[d] * prime[d] > N:
            break
        p = 0
        while N % prime[d] == 0:
            p += 1
            N //= prime[d]
        if p:
            p = (p * m) % mod
            p = (p + 1) % mod
            P = (P * p) % mod
    
    if N > 1:
        p = 1
        p = (p * m) % mod
        p = (p + 1) % mod
        P = (P * p) % mod
    
    return P

def nrdivk1_2(N):
    P = 1
    p = 0
    d = 0
    
    while N % 2 == 0:
        N //= 2
        p += 1
    
    P = (P * p) % mod
    
    for d in range(nrp):
        if prime[d] * prime[d] > N:
            break
        p = 0
        while N % prime[d] == 0:
            p += 1
            N //= prime[d]
        if p:
            p = (p + 1) % mod
            P = (P * p) % mod
    
    if N > 1:
        P = (P * 2) % mod
    
    return P

def solve(N, K):
    global mod
    if K % 2 == 0:
        nr1 = nrdivkn(K, N + 1)
        nr2 = nrdivk1(K + 1)
        return (nr1 * nr2) % mod
    else:
        nr1 = nrdivkn_2(K, N + 1)
        nr2 = nrdivk1_2(K + 1)
        return (nr1 * nr2) % mod

def read_solve():
    global mod
    with open("input.txt", "r") as f, open("output.txt", "w") as g:
        nr = int(f.readline())
        ver(nr)
        for _ in range(nr):
            n, k = map(int, f.readline().split())
            m = n + 1
            result = solve(n, k)
            g.write(str(result) + '\n')

mod = 1000000007
precalculation()
read_solve()