Cod sursa(job #3276719)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 14 februarie 2025 11:54:29
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <fstream>
#include <bitset>

using namespace std;

const int NMAX = 1e6;

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

int c, d;
long long sol;

short v[NMAX]; ///v[i] => Produsul a cator numere prime distincte mai mici decat i este egal cu i (asemanator pb pinex pe infoarena)

void solutie(int i)
{
    long long a = 0, b = 0;
    if(!v[i]) /// i este prim
    {
        for(int j = i; j <= d; j += i)
        {
            ++v[j];
            if(j <= c) ++a; ///Merg (i, j) si (j, i)
            else ++b; ///Merge doar (i, j)
        }
        sol += a * (a + b);
    }
    else if (v[i] != 1) /// i nu este divizibil cu patratul unui nr prim
    {
        for(int j = i; j <= d; j += i)
        {
            --v[j];
            if(j <= c) ++a; /// Merg (i, j) si (j, i)
            else ++b; /// Merge doar (i, j)
        }
        sol -= a * (a + b);
    }
}

int main()
{
    fin >> c >> d;
    --c, --d;
    if(c > d) swap(c, d);
    for(int i = 2; i <= c; ++i) solutie(i);
    fout << (long long)c*d - sol;
    return 0;
}