Editing 2494 - Desc Mult

==Cerința==
Se consideră două șiruri <code>D=(D1,D2,...,Dn)</code> și <code>E=(E1,E2,... ,En)</code> ce reprezintă descompunerea în factori primi pentru un număr natural nenul <code>X</code>, după cum urmează: <code>Di</code> – factorul prim, <code>Ei</code> – puterea la care apare factorul prim <code>Di</code> în descompunerea numărului <code>X (1≤i≤n)</code>, unde <code>n</code> reprezintă numărul factorilor primi.

Să se determine:

1. numărul total de divizori naturali ai lui <code>X</code>

2. divizorii lui <code>X</code> care aparțin intervalului <code>[A,B]</code>, unde <code>A</code> și <code>B</code> sunt două numere naturale date.

==Date de intrare==
Fișierul de ieșire <code>descmult.in</code> conține pe prima linie un număr natural <code>C</code> care reprezintă cerința ce trebuie rezolvată (<code>C=1</code> sau <code>C=2</code>).

A doua linie conține, despărțite prin câte un spațiu, trei numere naturale <code>n A B</code>, cu semnificația din enunț.

Pe linie a treia se află <code>n</code> numere naturale, separate prin câte un spațiu, ce reprezintă factorii primi <code>D1 D2 ... Dn</code> din descompunerea lui <code>X</code>.

Pe linia a patra se află <code>n</code> numere naturale, separate prin câte un spațiu, ce reprezintă puterile la care apar acești factori <code>E1 E2 ... En</code>.

==Date de ieșire==
Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse."

Pentru <code>C=1</code> se va rezolva doar prima cerință. În acest caz, pe următorul rând se va afișa un singur număr natural nenul ce reprezintă numărul total de divizori naturali ai lui <code>X</code>.

Pentru <code>C=2</code> se va rezolva cea de-a doua cerință. În acest caz, pe următorul rând se va afișa, separați prin câte un spațiu, divizorii lui <code>X</code> ce aparțin intervalului <code>[A,B]</code>.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Datele de intrare nu corespund restricțiilor impuse."

==Restricții și precizări==

* <code>2 ≤ n ≤ 20</code>
* <code>1 ≤ A ≤ B ≤ 107</code>

* <code>2 ≤ Di < 1000</code> (numere prime distincte), <code>1≤i≤n</code>

* <code>1 ≤ Ei ≤ 10</code>, <code>1≤i≤n</code>

* Se garantează că numărul maxim de divizori naturali ai lui <code>X ≤ 10</code> <code>19</code>
* Intervalul <code>[A,B]</code> conține cel puțin un divizor
* Numărul maxim de divizori aflați în intervalul <code>[A,B]</code> este <code>≤ 10</code> <code>6</code>
* Ordinea de afișare a divizorilor nu este importantă
* Pentru rezolvarea corectă a cerinței <code>1</code> se acordă <code>20</code> de puncte, iar pentru cea de-a doua cerință se acordă <code>80</code> de puncte.

==Exemplu 1==
;Intrare
:1
:4 30 50
:3 2 5 11
:1 3 2 1
;Ieșire
:Datele de intrare corespund restricțiilor impuse.
:48

===Explicație===
<code>X=31*23*52*111=6600</code> și are <code>48</code> de divizori: <code>1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 15, 20, 22, 24, 25, 30, 33, 40, 44, 50, 55, 60, 66, 75, 88, 100, 110, 120, 132, 150, 165, 200, 220, 264, 275, 300, 330, 440, 550, 600, 660, 825, 1100, 1320, 1650, 2200, 3300, 6600</code>.

==Exemplu 2==
;Intrare
:2
:4 30 50
:3 2 5 11
:1 3 2 1
;Ieșire
:Datele de intrare corespund restricțiilor impuse.
:30 44 50 40 33

===Explicație===
<code>X=31*23*52*111=6600</code>.

Divizorii ce aparțin intervalului <code>[30,50]</code> sunt: <code>30,33,40,44,50</code>. Ordinea de afișare a divizorilor nu este importantă.

==Exemplu 3==
;Intrare
:1
:4 30 50
:3 2 5 11
:1 10 15 1
;Ieșire
:Datele de intrare nu corespund restricțiilor impuse.

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2494 Desc Mult

def conditii(n, A, B, nr_naturale_factori_primi, nr_naturale_puteri):
    if not 2 <= n <= 20:
        return False
    if not len(nr_naturale_puteri) == len(nr_naturale_factori_primi) == n:
        return False
    if not 1 <= A <= B <= 10**7:
        return False

    for nr_f_p in nr_naturale_factori_primi:
        if not 2 <= nr_f_p < 1_000:
            return False

    for nr_n_p in nr_naturale_puteri:
        if not 1 <= nr_n_p <= 10:
            return False

    return True


def divizori(n, nr_naturale_puteri):
    # Calculăm numărul de divizori ai unui număr cu factorizarea în factori primi
    nr_divizori = 1
    for i in range(n):
        nr_divizori *= nr_naturale_puteri[i] + 1

    return nr_divizori


def divizori_interval(n, nr_naturale_puteri, nr_naturale_factori_primi, a, b):
    # Găsim divizorii unui număr în intervalul [a, b]
    x = 1
    for i in range(n):
        x *= (nr_naturale_factori_primi[i] ** nr_naturale_puteri[i])

    divizori_solutie = []
    # Pentru fiecare număr din intervalul [a, b]...
    for i in range(a, b+1):
        # ... verificăm dacă este divizor al lui x
        if x % i == 0:
            # Dacă da, îl adăugăm în lista de soluții
            divizori_solutie.append(i)

    return " ".join([str(x) for x in sorted(divizori_solutie)])


def descmult(c, n, A, B, nr_naturale_factori_primi, nr_naturale_puteri):
    # c este numărul cerinței
    if c == 1:
        print(divizori(n, nr_naturale_puteri))
    elif c == 2:
        print(divizori_interval(n, nr_naturale_puteri, nr_naturale_factori_primi, A, B))


if __name__ == "__main__":
    c = int(input())
    n, A, B = [int(x) for x in input().split()]
    nr_naturale_factori_primi = [int(x) for x in input().split()]
    nr_naturale_puteri = [int(x) for x in input().split()]

    if not conditii(n, A, B, nr_naturale_factori_primi, nr_naturale_puteri):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        descmult(c, n, A, B, nr_naturale_factori_primi, nr_naturale_puteri)

</syntaxhighlight>