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

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