Cod sursa(job #3276720)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 14 februarie 2025 11:55:29
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 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)

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