Fişierul intrare/ieşire:adn.in, adn.outSursăONI 2017 baraj gimnaziu
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test2 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Adn (baraj gimnaziu)

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={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.

Cerinţă

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 ≤ XN şi 1 ≤ YN.

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 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.

Exemple

adn.inadn.outExplicaţii
6
16
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)
19
88
 
38
251
 
99
961
 
Trebuie sa te autentifici pentru a trimite solutii. Click aici