0711 - Desc

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.

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.

Rezolvare

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