Kilonova
Toggle theme

adn

Time limit: 0.3s Memory limit: 64MB Input: adn.in Output: adn.out

Pe Marte s-au descoperit NN marțieni, identificați de către oamenii de știință de pe Pământ prin numerele de la 11 la NN. Cercetările au dovedit că ADN-ul oricărui marțian XX este format din mulțimea factorilor primi din descompunerea lui XX. De exemplu ADN(6)={2,3}\text{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 XX dacă ADN(X)\text{ADN}(X) este inclus în ADN(Y)\text{ADN}(Y), adică mulțimea factorilor primi ai lui XX este inclusă în mulțimea factorilor primi ai lui YY. De exemplu, marțianul 66 îl moștenește pe marțianul 33 deoarece ADN(3)={3}\text{ADN}(3)=\{3\} este inclus în ADN(6)={2,3}\text{ADN}(6)=\{2,3\}.

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

Cerință

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

Date de intrare

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

Date de ieșire

Fișierul de ieșire adn.out va conține pe prima linie numărul de perechi determinat.

Restricții și precizări

  • 1≤N≤5⋅1061 \leq N \leq 5 \cdot 10^6.
  • Pe planeta Marte orice marțian X îl moștenește pe X.
  • Orice marțian îl moștenește pe marțianul 11 deoarece ADN(1)={}\text{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.

Exemplul 1

adn.in

6

adn.out

16

Explicație

ADN(1)={}\text{ADN}(1)=\{\}, ADN(2)={2}\text{ADN}(2)=\{2\}, ADN(3)={3}\text{ADN}(3)=\{3\}, ADN(4)={2}\text{ADN}(4)=\{2\}, ADN(5)={5}\text{ADN}(5)=\{5\}, ADN(6)={2,3}\text{ADN}(6)=\{2,3\}
Perechile de marțieni determinate sunt (1,1)(1,1); (2,2)(2,2); (3,3)(3,3); (4,4)(4,4); (5,5)(5,5); (6,6)(6,6); (4,2)(4,2); (2,4)(2,4); (6,2)(6,2); (6,3)(6,3); (6,4)(6,4); (2,1)(2,1); (3,1)(3,1); (4,1)(4,1); (5,1)(5,1); (6,1)(6,1).

Exemplul 2

adn.in

19

adn.out

88

Exemplul 3

adn.in

38

adn.out

251

Exemplul 4

adn.in

99

adn.out

961

Log in or sign up to be able to send submissions!