RebecaBud: Pagină nouă: == Enunt == 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 == 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...

2024-06-03T17:00:44Z

Pagină nouă: == Enunt == 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 == 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...

New page

== Enunt ==
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 ==
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 ==
Fișierul de intrare desc.in conține pe prima linie numărul n.
== Date de ieșire ==
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 ==
* '''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 ==
; desc.in

10
; desc.out

2 2 1 3
3 2 0 2
== Explicație ==
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.
<br>

== Exemplul 2 ==
; desc.in

11
; desc.out

2 3 0 1 3
11 1 1
== Explicație ==
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.
<br>

== Rezolvare ==
<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>

0711 - Desc - Revision history