Soluții trimise

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.

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.

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.

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.