2148 - ADN

Cerința

Pe Marte s-au descoperit N marțieni, identificați de către oamenii de știință de pe Pământ prin numerele de la 1 la N. Cercetările au dovedit că ADN-ul oricărui marțian X este format din mulțimea factorilor primi din descompunerea lui X. De exemplu ADN(6)={2,3}.

Se știe că marțianul cu numărul de ordine Y îl moștenește pe marțianul cu numărul de ordine X dacă ADN(X) este inclus în ADN(Y), adică mulțimea factorilor primi ai lui X este inclusă în mulțimea factorilor primi ai lui Y.

De exemplu, marțianul 6 îl moștenește pe marțianul 3 deoarece ADN(3)={3} este inclus în ADN(6)={2,3}.

Trebuie să specificăm că se pot întâlni situații extreme în care X îl moștenește pe Y dar și Y îl moștenește pe X, atunci când cei doi marțieni au ADN-urile egale. Este situația marțianului 12 care îl moștenește pe 6 dar și 6 îl moștenește pe 12.

Realizați un program care, considerând mulțimea celor N marțieni, determină numărul de perechi de marțieni (Y, X) pentru care Y îl moștenește pe X, unde 1 ≤ X ≤ N și 1 ≤ Y ≤ N.

Date de intrare

Fișierul de intrare adn.in conține pe prima linie numărul N, reprezentând numărul de marțieni.

Date de ieșire

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

Pe următorul rând se va afișa numărul de perechi determinat.

Î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 ≤ 5 000 000
• Pe planeta Marte orice marțian X îl moștenește pe X.
• Orice marțian îl moștenește pe marțianul 1 deoarece ADN(1)={}, adică mulțimea vidă, care se consideră inclusă în orice mulțime nevidă.
• Se garantează că numărul de perechi determinat are cel mult nouă cifre.

Exemplu 1

Intrare

6

Ieșire

Datele de intrare corespund restricțiilor impuse.

16

Explicație

ADN(1)={}, ADN(2)={2}, ADN(3)={3}, ADN(4)={2}, ADN(5)={5}, ADN(6)={2,3}.

Perechile de marțieni determinate sunt (1,1); (2,2); (3,3); (4,4); (5,5); (6,6); (4,2); (2,4); (6,2); (6,3); (6,4); (2,1) ; (3,1); (4,1); (5,1); (6,1).

Exemplu 2

Intrare

19

Ieșire

Datele de intrare corespund restricțiilor impuse.

88

Exemplu 3

Intrare

38

Ieșire

Datele de intrare corespund restricțiilor impuse.

251

Exemplu 4

Intrare

99

Ieșire

Datele de intrare corespund restricțiilor impuse.

961

Exemplu 5

Intrare

0

Ieșire

Datele de intrare nu corespund restricțiilor impuse.

Rezolvare

#2148 ADN
def conditii(n):
    return 1 <= n <= 5_000_000


def ADN(n):
    martieni_adn = {}
    nr_perechi = 0

    # Inițializăm un dicționar cu cheile de la 1 la n și valorile 1
    for i in range(1, n + 1):
        martieni_adn[i] = 1

    # Folosim Ciurul lui Eratostene pentru a calcula factorizarea în numere prime a fiecărui număr de la 2 la n
    for i in range(2, n + 1):
        # Dacă martieni_adn[i] == 1, atunci i este un număr prim
        if martieni_adn[i] == 1:
            # Setăm factorizarea în numere prime a lui martieni_adn[i] să fie pasul i
            martieni_adn[i] = i
            # Folosind algoritmul Ciurului lui Eratostene, marcam toți multiplii lui i cu factorul prim i
            j = 2
            while j * i <= n:
                martieni_adn[i * j] = martieni_adn[i * j] * i
                # Incrementăm j pentru a considera următorul multiplu al lui i
                j += 1

    # Calculăm numărul de perechi de marțieni cu ADN-e distincte
    for i in range(1, n + 1):
        nr_perechi += int(n / martieni_adn[i])

    print(nr_perechi)


if __name__ == "__main__":
    n = int(input())

    if not conditii(n):
        print("Datele de intrare nu corespund restricțiilor impuse.")
    else:
        print("Datele de intrare corespund restricțiilor impuse.")
        ADN(n)