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
Pentru C=1 se va rezolva doar prima cerință. În acest caz, fișierul de ieșire descmult.out va conține pe prima linie 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, fișierul de ieșire descmult.out va conține, separați prin câte un spațiu, divizorii lui X ce aparțin intervalului [A,B].
Restricții și precizări
2 ≤ n ≤ 201 ≤ 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 ≤ 1019 - Intervalul
[A,B]conține cel puțin un divizor - Numărul maxim de divizori aflați în intervalul
[A,B]este≤ 106 - Ordinea de afișare a divizorilor nu este importantă
- Pentru rezolvarea corectă a cerinței
1se acordă20de puncte, iar pentru cea de-a doua cerință se acordă80de puncte.
Exemplu 1
- Intrare
- 1
- 4 30 50
- 3 2 5 11
- 1 3 2 1
- Ieșire
- 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
- 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
- Date de intrare gresite!
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):
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):
x = 1
for i in range(n):
x *= (nr_naturale_factori_primi[i] ** nr_naturale_puteri[i])
divizori_sol = []
for i in range(a, b+1):
if x % i == 0:
divizori_sol.append(i)
return " ".join([str(x) for x in sorted(divizori_sol)])
def 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):
return print("Date de intrare gresite!")
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__":
main()
</syntaxhighlight>