Rezolvare completă PbInfo #2148 ADN

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ța

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.

Date de intrare

Fișierul de intrare adn.in conține pe prima linie numărul 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.

Exemplul 1

adn.in

6

adn.out

16

Explicație

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

Exemplul 2

adn.in

19

adn.out

88

Exemplul 3

adn.in

38

adn.out

251

Exemplul 4

adn.in

99

adn.out

961

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema ADN:

#include <fstream>
#include <cassert>

using namespace std;

#define MAXN 5000010

int Base[MAXN];
int N;
int ans;

int main() {
    ifstream in("adn.in");
    ofstream out("adn.out");

    in >> N;
    assert(N<=5000000 && N > 0);
    for (int i = 1; i <= N; ++i)
        Base[i] = 1;
    for (int i = 1; i <= N; ++i) {
        if (Base[i] != 1) continue;

        for (int j = i; j <= N; j += i)
            Base[j] *= i;
    }

    for (int i = 1; i <= N; ++i)
        ans += (N / Base[i]);

    out << ans;
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #2148 ADN

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2148 ADN de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!