Fișierul intrare/ieșire adn.in, adn.out Sursă ONI 2017 baraj gimnaziu
Autor autor necunoscut Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 2 sec Limită de memorie 32768 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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

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.in adn.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii