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

<syntaxhighlight lang="python3" line="1"> 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()

</syntaxhighlight>