3522 - Nr Div Huge - Revision history

Corjuc Eunice: Pagină nouă: = 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
2024-01-04T17:51:38Z

Pagină nouă: = Cerința = Se dau <code>N</code> perechi de numere <code>n k</code>. Pentru fiecare pereche să se calculeze numărul de divizori al lui . = Date de intrare = Fișierul de intrare <code>input.txt</code> conține pe prima linie numărul <code>N</code>, iar pe următoarele <code>N</code> linii <code>N</code> perechi de numere <code>n</code> și <code>k</code> separate printr-un spațiu. = Date de ieșire = Fișierul de ieșire <code>output.txt</code> va conține pe linia <c...

New page
= Cerința =
Se dau <code>N</code> perechi de numere <code>n k</code>. Pentru fiecare pereche să se calculeze numărul de divizori al lui .

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

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

= Restricții și precizări =

* <code>1 ≤ N ≤ 15.000</code>

== Exemplul 1 ==
input.txt:

2

2 3

4 4

output.txt:

8

20

Explicație:

Pentru prima pereche: <code>P=54</code>, iar <code>54</code> are <code>8</code> divizori.

Pentru cea de-a doua pereche: <code>P=2560</code>, iar <code>2560</code> are <code>20</code> 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>