2494 - Desc Mult

Cerința

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

Să se determine:

1. numărul total de divizori naturali ai lui X

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

Date de intrare

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

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

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

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

Date de ieșire

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

Pentru C=1 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 X.

Pentru C=2 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 X ce aparțin intervalului [A,B].

Î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

• 2 ≤ n ≤ 20
• 1 ≤ A ≤ B ≤ 107

• 2 ≤ Di < 1000 (numere prime distincte), 1≤i≤n

• 1 ≤ Ei ≤ 10, 1≤i≤n

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

X=31*23*52*111=6600 și are 48 de divizori: 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.

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

X=31*23*52*111=6600.

Divizorii ce aparțin intervalului [30,50] sunt: 30,33,40,44,50. 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

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