0955 - Miny
Fie N
un număr natural nenul şi N
numere naturale nenule: x1
, x2
,…, xN
.
Fie P
produsul acestor N numere, P=x1•x2•...•xN
.
Cerinţe
Scrieţi un program care să citească numerele N
, x1
, x2
,…, xN
şi apoi să determine:
a) cifra zecilor produsului P
;
b) cel mai mic număr natural Y
, pentru care există numărul natural K
astfel încât YK=P
.
Date de intrare
Fișierul de intrare input.txt
conţine două linii. Pe prima linie este scris numărul natural N
. Pe următoarea linie sunt scrise cele N
numere naturale x1
, x2
,…, xN
, separate prin câte un spaţiu.
Date de ieșire
Fișierul de ieșire output.txt
va conține:
- pe prima linie o cifră reprezentând cifra zecilor produsului
P
; - pe a doua linie numărul natural M de factori primi din descompunerea în factori primi a numărului
Y
; - pe fiecare dintre următoarele
M
linii (câte o linie pentru fiecare factor prim din descompunere) câte două valoriF
şiE
, separate printr-un singur spaţiu,F
reprezentând factorul prim iarE
exponentul acestui factor din descompunerea în factori primi a luiY
; scrierea în fişier a acestor factori primi se va face în ordinea crescătoare a valorii lor.
Restricții și precizări
2 ≤ N ≤ 50000
Exemplul 1
input.txt:
6
12 5 60 25 4 36
output.txt:
0
3
2 2
3 1
5 1
Explicație:
Produsul celor 6
numere este: P=12∙5∙60∙25∙4∙36=12960000
.
Cifra zecilor lui P este 0
.
Se observă că există 3
valori posibile pentru Y
: 12960000
, 3600
şi 60
deoarece: 129600001=12960000
, 36002=12960000
, 604=12960000
.
Cea mai mică valoare dintre aceste valori este 60
, astfel Y=60=(2**2)*3*5
.
Exemplul 2
input.txt:
3
2 5 7
output.txt:
7
3
2 1
5 1
7 1
Explicație:
Produsul celor 3
numere este: P=2∙5∙7=70
. Cifra zecilor lui P este 7
. Există o singură valoare posibilă pentru Y
: 70
.
Exemplul 3
input.txt:
999999999999
2 5 7
Output:
Input-ul nu convine conditiilor
Rezolvare
def verificare(n):
if not(2<=n<=5000):
print("Input-ul nu convine conditiilor")
exit()
def cmmdc(a, b):
while a and b:
if a > b:
a = a % b
else:
b = b % a
return a + b
n = 10000
v = [0] * (n + 1)
fr = [0] * (n + 1)
w = [0] * (n + 1)
# determinare numere prime <=10000 - Ciurul lui Eratostene
v[2] = 1
for i in range(3, n + 1, 2):
v[i] = 1
for i in range(3, n + 1, 2):
if v[i] != 0:
for j in range(2 * i, n + 1, i):
v[j] = 0
with open("input.txt", "r") as f, open("output.txt", "w") as g:
N = int(f.readline())
verificare(N)
l=list(map(int, f.readline().split()))
p = 1
for i in range(N):
x = l[i]
fr[x] += 1
p = (p * x) % 100
for i in range(2, n + 1):
if fr[i]:
if v[i]:
w[i] += fr[i]
else:
x = i
for j in range(2, n + 1):
while v[j] and (x % j == 0) and x > 1:
w[j] += fr[i]
x //= j
M = 0
d = 0
for i in range(2, n + 1):
if w[i]:
M += 1
d = cmmdc(d, w[i])
g.write(f"{p // 10}\n{M}\n")
for i in range(2, n + 1):
if w[i]:
g.write(f"{i} {w[i] // d}\n")