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ă valori F şi E, separate printr-un singur spaţiu, F reprezentând factorul prim iar E exponentul acestui factor din descompunerea în factori primi a lui Y; 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

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

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")

</syntaxhighlight>