Editing 2148 - ADN


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

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

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

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

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

==Date de intrare==
Fișierul de intrare <code>adn.in</code> conține pe prima linie numărul <code>N</code>, reprezentând numărul de marțieni.
==Date de ieșire==
Fișierul de ieșire <code>adn.out</code> va conține pe prima linie numărul de perechi determinat.

==Restricții și precizări==

* <code>1 ≤ N ≤ 5 000 000</code>
* <code>Pe planeta Marte orice marțian X îl moștenește pe X.</code>
* <code>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ă.</code>
* <code>Se garantează că numărul de perechi determinat are cel mult nouă cifre.</code>

==Exemplu 1==
;Intrare
:6
;Ieșire
:16

===Explicație===
<code>ADN(1)={}</code>, <code>ADN(2)={2}</code>, <code>ADN(3)={3}</code>, <code>ADN(4)={2}</code>, <code>ADN(5)={5}</code>, <code>ADN(6)={2,3}</code>.

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

==Exemplu 2==
;Intrare
:19
;Ieșire
:88

==Exemplu 3==
;Intrare
:38
;Ieșire
:251

== Exemplu 4 ==
;Intrare
:99
;Ieșire
:961

== Exemplu 5 ==
;Intrare
:0
;Ieșire
:Date de intrare gresite!

==Rezolvare==
<syntaxhighlight lang="python" line="1">
#2148 ADN
def conditii(n):
    return 1 <= n <= 5_000_000


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

    for i in range(1, n + 1):
        martieni_adn[i] = 1
    for i in range(2, n + 1):
        if martieni_adn[i] == 1:
            martieni_adn[i] = i
            j = 2
            while j * i <= n:
                martieni_adn[i * j] = martieni_adn[i * j] * i
                j += 1
    for i in range(1, n + 1):
        nr_perechi += int(n / martieni_adn[i])

    return nr_perechi


def main():
    n = int(input())

    if not conditii(n):
        return print("Date de intrare gresite!")

    print(nr_perechi_adn(n))


if __name__ == "__main__":
    main()

</syntaxhighlight>