Editing 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>
#3680 - Numere X
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>