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

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