Cod sursa(job #3359281)

Utilizator mariusn01Marius Nicoli mariusn01 Data 26 iunie 2026 15:08:41
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <fstream>
#define DIM 1000100

using namespace std;

long long c, d, sol, i, j, m, x;

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

long long ciur1[DIM];
long long ciur2[DIM];

/// cum pot decide mai repede decat n radical(n) daca un numar de pana in n e liber de patrate (produs de factori primi distincri)
/// 5 * 7^3 se divide prin 7^2 (nu e liberde patrate)




int main () {
    ifstream fin ("mins.in");
    ofstream fout("mins.out");

    fin>>c>>d;

    c--;
    d--;

    m = min(c,d);
    for (i=2;i<=m;i++)
        if (ciur1[i] == 0)
            for (j=i;j<=m;j+=i)
                ciur1[j]++; /// ciur1[numar] = numarul de factori primi ai lui "numar"

    for (i=2;i<=m;i++)
        if (ciur1[i] == 1) /// daca e prim
            for (j=i*i;j<=m;j+=i*i)
                ciur2[j] = 1; /// marchez in ciur2 doar multiplii patratelor de numere prime
    sol = c*d;

    for (x=2;x<=min(c,d);x++)
        if ( ciur2[x] == 0 ) /// x este produs de factori primi distincti
            if (ciur1[x] % 2 == 1) ///x are numar impar de factori primi
                sol -= f(x);
            else
                sol += f(x);

    fout<<sol;

    return 0;
}


/**
    for (i=1;i<=c;i++)      5000 * 5000 * log
        for (j=1;j<=d;j++)
            if (gcd(i,j) == 1)
                sol++;
    **/