0711 - Desc

From Bitnami MediaWiki

Enunt[edit | edit source]

Fie n un număr natural nenul, n > 1. Definim n(p) ca fiind descompunerea lui n în sumă de puteri naturale distincte ale numărului prim p.

Exemple:

  • pentru n=10 toate n(p) descompunerile posibile sunt: 10(2)=21+23 şi 10(3)=30+32
  • pentru n=11 toate n(p) descompunerile posibile sunt: 11(2)=20+21+23 şi 11(11)=111

Cerinţa[edit | edit source]

Să se scrie un program care citeşte un număr natural n şi determină toate n(p) descompunerile numărului n.

Date de intrare[edit | edit source]

Fișierul de intrare desc.in conține pe prima linie numărul n.

Date de ieșire[edit | edit source]

Fișierul de ieșire desc.out va conține pe linii separate toate n(p) descompunerile numărului n. Fiecare linie va conţine în ordine:

  • o valoare naturală p reprezentând numărul prim asociat descompunerii;
  • o valoare naturală k, reprezentând numărul de termeni ai descompunerii;
  • Următoarele k valori, numere naturale, reprezintă exponenţii puterilor din descompunere, scrise în ordine crescătoare.

Restricţii şi precizări[edit | edit source]

  • 2 ≤ n ≤ 10 000 000
  • Pentru un număr prim p fixat, există o singură n(p) descompunere a unui număr natural n;
  • Descompunerile vor fi afişate în ordinea crescătoare a valorilor identificate pentru p;
  • Pe fiecare linie a fişierului de ieşire, valorile vor fi despărţite prin câte un spaţiu.

Exemplul 1[edit | edit source]

desc.in
 10
desc.out
 2 2 1 3
 3 2 0 2

Explicație[edit | edit source]

10(2)=21+23; 10(3)=30+32. Prima descompunere s-a făcut după numărul prim p=2 şi conţine 2 termeni cu puterile 1 şi 3. A doua descompunere s-a făcut după numărul prim p=3 şi conţine 2 termeni cu puterile 0 şi 2.

Exemplul 2[edit | edit source]

desc.in
 11
desc.out
 2 3 0 1 3 
 11 1 1 

Explicație[edit | edit source]

11(2)=20+21+23; 11(11)=111. Prima descompunere s-a făcut după numărul prim p=2 şi conţine 3 termeni cu puterile 0, 1 şi 3. A doua descompunere s-a făcut după numărul prim p=11 şi conţine un termen cu puterea 1.

Rezolvare[edit | edit source]

<syntaxhighlight lang="python" line> def prime_factors(n):

   factors = []
   d = 2
   while d * d <= n:
       while n % d == 0:
           factors.append(d)
           n //= d
       d += 1
   if n > 1:
       factors.append(n)
   return factors

def decompose(n):

   primes = prime_factors(n)
   decompositions = []
   for p in set(primes):
       exponents = []
       count = primes.count(p)
       for i in range(count):
           exponents.append(i)
       decompositions.append((p, count, exponents))
   return sorted(decompositions)

def main():

   with open("desc.in", "r") as fin:
       n = int(fin.readline())
   decompositions = decompose(n)
   with open("desc.out", "w") as fout:
       for decomposition in decompositions:
           p, k, exponents = decomposition
           fout.write(f"{p} {k} {' '.join(map(str, exponents))}\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>