Cod sursa(job #3359044)

Utilizator mariusn01Marius Nicoli mariusn01 Data 23 iunie 2026 12:32:33
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <fstream>

using namespace std;

long long ciur1[1000010], ciur2[1000010];
long long c, d, i, j, sol, m;

long long f(long long x) {
    return (c/x)*(d/x);
}

int main () {
    ifstream fin ("mins.in");
    ofstream fout("mins.out");
    fin>>c>>d;
    c--;
    d--;

    m = min(c,d); /// fac ciur pana la minimul dlong longre c si d pentru ca la numerele prime mai mari ca acest minim functia f va returna 0
    for (i=2;i<=m;i++)
        if (ciur1[i] == 0)
            for (j=i;j<=m;j+=i)
                ciur1[j] ++; /// toti multiplii lui i il au factor prim pe i
    /// raman marcate cu 0 numerele prime
    /// si elementele nenule sunt chiar numarul de factori primi

///    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
///    1 1 1 1 2 1 1 1  2  1  2  1  2  2  1  1  2  1  2

    sol = c*d;

    /**
    sol -= (suma din f(numar prim))
    sol += (suma din f(produs de 2 numere prime distincte)) /// ne itereseaza 6 dar nu 12 sau 18
                                                            /// ne long longereseaza 21 (3*7) dar nu si 42 sau 63
    sol -= (suma din f(produs de 3 numere prime distincte)) etc

    Mai sus cu ciur am depistat numerele care sunt prime.
    Pe mine ma long longereseaza mai mult:
        - si numerele care sunt produs de numere prime disticte
        - si produs de cati factori primi distincti sunt aceste numere ca

    **/



    /**
    c = 9 si d = 12
    sol = 9*12
    sol -= f(2) /// eliminam toate perechile de numere cu cmmdc 2
    sol -= f(3) /// eliminam toate perechile de numere cu cmmdc 3
    4 nu ne long longereseaza
    sol -= f(5) /// eliminam toate perechile de numere cu cmmdc 5
    sol += f(6) /// punem la loc perechi de numere cu cmmdc 6
    sol -= f(7) /// eliminam toate perechile de numere cu cmmdc 7
    8 nu ne long longereseaza
    9 nu ne long longereseaza
    **/

    /**
    Ramane decizia daca un numar este sau nu produs de factori primi distincti si de cati astfel de factori ca paritate
    solutia 1: factorizez cu descompunere in factori primi fiecare numar pana la 1000000 si numar ce imi trebuie
    1000000 * sqrt(1000000) teoretic duce la miliard
    **/

    /**
    Vom face altfel observand ca numerele rele sunt divizibile prlong longr-un patrat perfect de numar prim
    Adica daca numarul nu e [rodus de factori primi distincti inseamna ca cel putin un factor prim apare in el cel putin la puterea a 2-a
    Ex 40 = 2 ^ 3 * 5 se divide prim 2 ^ 2
    **/

    for (i=2;i<=m;i++)
        if(ciur2[i] == 0)
            for (j=i*i; j<=m; j+= i*i )
                ciur2[j] = 1;
    /// am marcat in ciur2 cu 1 numerele care nu sunt libere de patrate (divizibile prin cel putin un FP la o putere mai mare ca 1)

    for (i=2;i<=m;i++)
        if (ciur2[i] == 0) ///i este produs de factori primi distincti
            if (ciur1[i] % 2 == 1) /// i are numar impar de factori primi
                sol -= f(i);
            else
                sol += f(i);
/**
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
          1       1 1        1           1     1
**/
    fout<<sol;
}