3680 - Numere X

Enunţ

Pentru un număr natural nenul X, se numește divizor propriu al lui X, un divizor natural al lui X, diferit de 1 și X. De exemplu, pentru numărul 20 divizorii proprii sunt 2, 4, 5, 10, iar numărul 20 are 4 divizori proprii.

Cerința

1. Se dă un număr natural N. Determinați cel mai mic număr din intervalul închis [1,N] care are număr maxim de divizori proprii. 2. Se dau trei numere N, M și T. Determinați câte intervale de forma [a,b] au proprietatea că există exact M numere naturale care au T divizori proprii.

Date de intrare

Fișierul de intrare numere.in conține pe prima linie un număr natural P reprezentând cerința din problemă care trebuie rezolvată.

Dacă P = 1 atunci pe a doua linie se găsește un număr natural N, reprezentând extremitatea din dreapta a intervalului.

Dacă P = 2 atunci pe a doua linie se găsesc trei numere: un număr natural N, un număr natural M și un număr natural T cu semnificațiile din enunț.

Date de ieșire

Dacă P = 1 atunci fișierul de ieșire numere.out conține pe o singură linie numărul cel mai mic determinat care are număr maxim de divizori.

Dacă P = 2 atunci fișierul de ieșire numere.out conține pe o singură linie numărul de intervale determinate care au proprietatea cerută.

Restricții și precizări

• 1 ≤ N ≤ 100000
• 1 ≤ M ≤ 100000
• 1 ≤ T ≤ 100000
• 1 ≤ a ≤ b ≤ N

Exemplul 1

numere.in

1

20

numere.out

12

Explicație

12 are 4 divizori proprii și este cel mai mic număr cu 4 divizori proprii din [1,20].

Exemplul 2

numere.in

2

10 3 2

numere.out

6

Explicație

[1,10], [2,10], [3,10], [4,10], [5,10], [6,10] sunt cele 6 intervale în care se găsesc exact 3 numere cu 2 divizori proprii(6, 8, 10 sunt numerele cu 3 divizori proprii).

Exemplul 3

numere.in

1

0

numere.out

Datele introduse sunt invalide

Rezolvare

<syntaxhighlight lang="python" line> def numar_divizori(n):

   divizori = 0
   for i in range(2, int(n**0.5) + 1):
       if n % i == 0:
           if n // i == i:
               divizori += 1
           else:
               divizori += 2
   return divizori

def cel_mai_mic_numar_cu_max_divizori(N):

   maxim_divizori = 0
   numar = 0
   for i in range(1, N + 1):
       divizori = numar_divizori(i)
       if divizori > maxim_divizori:
           maxim_divizori = divizori
           numar = i
   return numar

def numar_intervale_cu_M_numere_T_divizori(N, M, T):

   numar_intervale = 0
   for a in range(1, N + 1):
       for b in range(a, N + 1):
           numere_cu_T_divizori = sum(1 for x in range(a, b + 1) if numar_divizori(x) == T)
           if numere_cu_T_divizori == M:
               numar_intervale += 1
   return numar_intervale

def verifica_date_intrare(P, N, M, T):

   if P not in [1, 2]:
       return False
   if P == 1:
       if not isinstance(N, int) or N < 1 or N > 100000:
           return False
   elif P == 2:
       if not (isinstance(N, int) and isinstance(M, int) and isinstance(T, int)):
           return False
       if not (1 <= N <= 100000 and 1 <= M <= 100000 and 1 <= T <= 100000):
           return False
   return True

def main():

   N = None
   with open("numere.in", "r") as fin:
       P = int(fin.readline().strip())
       if P == 1:
           N = int(fin.readline().strip())
       elif P == 2:
           N, M, T = map(int, fin.readline().strip().split())

   if not verifica_date_intrare(P, N, M if P == 2 else None, T if P == 2 else None):
       with open("numere.out", "w") as fout:
           fout.write("Datele introduse sunt invalide\n")
       return

   if P == 1:
       rezultat = cel_mai_mic_numar_cu_max_divizori(N)
   else:
       rezultat = numar_intervale_cu_M_numere_T_divizori(N, M, T)

   with open("numere.out", "w") as fout:
       fout.write(str(rezultat) + "\n")

if __name__ == "__main__":

   main()

</syntaxhighlight>