2433 - Cufar

Cerința

Vrăjitoarea cea bună are un cufăr în care este închisă piatra magică de către piticii lăzii cu ajutorul unui cifru digital. Piticii i-au dat vrăjitoarei o cutie în care sunt n cartonașe. Pe fiecare cartonaș este scris un număr natural pe care vrăjitoarea îl va folosi să deschidă lada. Valorile scrise pe cartonașe sunt distincte între ele.

Pentru a afla cifrul trebuie să procedeze astfel: extrage fiecare cartonaș din cutie și apoi determină valoarea magică asociată numărului natural scris pe cartonaș. Pentru fiecare cartonaș valoarea magică este dată de al k-lea divizor prim al numărului înscris pe acesta. Vrăjitoarea trebuie să adune valorile magice obținute pentru cele n cartonașe și apoi să introducă în ordine cifrele valorii obținute, pentru a descuia lada.

Deoarece vrăjitoarea nu are timp la dispoziție vă roagă pe voi să o ajutați să rezolve următoarele probleme:

1. Să afle valoarea magică pentru un cartonaș dat;

2. Să afle cifrul cufărului.

Date de intrare

Fișierul de intrare este cufar.in. Pe prima linie a fișierului de intrare se găsesc o valoare p care poate fi doar 1 sau 2 și numărul n de cartonașe despărțite prin câte un spațiu.

Dacă p este 1 pe linia a doua a fișierului de intrare se găsesc două valori reprezentând numărul de pe cartonașul dat și valoarea k, separate printr-un spațiu, cu semnificația de mai sus.

Dacă p este 2 pe următoarele n linii ale fișierului de intrare se găsesc câte două valori, separate prin câte un spațiu, reprezentând numărul de pe cartonaș și valoarea lui k pentru fiecare din cele n cartonașe.

Date de ieșire

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

Dacă valoarea lui p este 1, atunci se va rezolva doar cerința 1 și pe următorul rând se va afișa valoarea magică asociată cartonașului dat.

Dacă valoarea lui p este 2, atunci se va rezolva doar cerința 2 și pe următorul rând se va afișa cifrul necesar deschiderii cufărului.

Î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

• 1 ≤ n < 1 000 000
• 2 ≤ valoarea înscrisă pe un cartonaș ≤ 1 000 000

• Se garantează că pentru fiecare pereche (număr, k), număr are cel puțin k divizori primi.

Exemplu 1

Intrare

1 1

30 3

Ieșire

Datele de intrare corespund restricțiilor impuse.

5

Explicație

p = 1, n = 1

Se rezolvă doar prima cerință. Al treilea divizor prim al numărului 30 este 5.

Exemplu 2

Intrare

2 5

30 3

64 1

105 2

1001 3

5474 4

Ieșire

Datele de intrare corespund restricțiilor impuse.

48

Explicație

p = 2, n = 5

Se rezolvă doar a doua cerință. Al treilea divizor prim al numărului 30 este 5.

Primul divizor prim al numărului 64 este 2.

Al doilea divizor prim al numărului 105 este 5.

Al treilea divizor prim al numărului 1001 este 13.

Al patrulea divizor prim al numărului 5474 este 23.

Suma căutată va fi S = 5 + 2 + 5 + 13 + 23, de unde rezultă cifrul 48.

Exemplu 3

Intrare

2 3

1 3

1000000 1

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#2433 Cufar
def conditie_n(n):
    return 1 <= n < 1_000_000


def conditie_cartonas(cartonas):
    return 2 <= cartonas < 1_000_000


def prim(nr):
    # Dace nr <= 1, atunci nr nu este prim.
    if nr < 2:
        return False
    # Dacă de la 2 până la rădăcina pătrată a lui nr există un divizor a lui nr, atunci nr nu este prim.
    for i in range(2, int(nr**0.5) + 1):
        if nr % i == 0:
            return False

    return True


def cufar(cartonas, k):
    nr = 0

    # Iterăm toate numerele de la 2 la cartonas
    for i in range(2, cartonas+1):
        # Dacă i este divizor al lui cartonas și este prim...
        if cartonas % i == 0 and prim(i):
            # ... incrementăm nr
            nr += 1
            # Dacă nr este egal cu k, atunci am găsit al k-lea divizor prim al lui cartonas
            if nr == k:
                return i

    return nr


if __name__ == "__main__":
    p, n = [int(x) for x in input().split()]

    if not conditie_n(n):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        # Iterăm de la 1 până la n
        suma = 0
        for i in range(n):
            # La fiecare iterație, citim 2 valori: cartonas și k
            cartonas, k = [int(x) for x in input().split()]
            if not conditie_cartonas(cartonas):
                print("Datele de intrare nu corespund restricțiilor impuse.")
                exit(0)
            # Adăugăm la variabila suma rezultatul funcției cufar
            suma += cufar(cartonas, k)

        print("Datele de intrare corespund restricțiilor impuse.")
        print(suma)