1474 - Exponent

Enunț

Softescu a învăţat azi la şcoală, la ora de informatică algoritmul determinării exponentului unui număr natural prim p în descompunerea în factori primi a lui n!. Softescu s-a gândit că ar fi interesant dacă ar putea să elaboreze un algoritm care să determine exponentul unui număr natural oarecare, a (a>1) în descompunerea în factori primi a lui n!.

Cerința

Dându-se două numere naturale n şi a, nenule, se cere să se determine exponentul numărului natural a în descompunerea lui n!.

Date de intrare

Fişierul de intrare exponentin.txt conţine pe prima linie două numere naturale, nenule, n a separate printr-un spațiu.

Date de ieșire

Fişierul de ieşire exponentout.txt va conţine pe prima linie un număr natural e, reprezentând exponentul numărului natural a în descompunerea în factori primi a lui n!

Restricții și precizări

• 2 ⩽ n, a ⩽ 1000
• exponentul unui număr natural nenul x, nu neapărat prim, în descompunerea unui număr natural nenul y este cel mai mare număr natural e cu proprietatea că xe este divizor al lui y.

Exemplul 1

Intrare

exponentin.txt

6 4

Ieșire

Datele de intrare corespund restricțiilor impuse

exponentout.txt

2

Explicație

6!=1*2*3*4*5*6 = 1*3*3*4*4*5.

Exemplul 2

Intrare

exponentin.txt

1 4

Ieșire

Datele de intrare NU corespund restricțiilor impuse

Rezolvare

<syntaxhighlight lang="python" line>

1. 1474 - Exponent

def validare_date(n, a):

   if not (2 <= n <= 1000 and 2 <= a <= 1000):
       return False
   return True

def exponent_in_descompunere(n, a):

   if validare_date(n, a):
       print("Datele de intrare corespund restricțiilor impuse")

       def calculeaza_exponent(prima_putere, numar):
           exponent = 0
           while numar % prima_putere == 0:
               exponent += 1
               numar //= prima_putere
           return exponent
       factorial_n = 1
       for i in range(2, n + 1):
           factorial_n *= i
       exponent_a = calculeaza_exponent(a, factorial_n)
       return exponent_a
   else:
       print("Datele de intrare NU corespund restricțiilor impuse")
       exit(0)

with open("exponentin.txt", "r") as file:

   n, a = map(int, file.readline().split())

with open("exponentout.txt", "w") as file:

   exponent_a = exponent_in_descompunere(n, a)
   file.write(str(exponent_a))

</syntaxhighlight>