Cod sursa(job #3276724)

Utilizator bogdan1479Luca Bogdan Alexandru bogdan1479 Data 14 februarie 2025 12:10:51
Problema Mins Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.14 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, a, b;

bitset<2> v[NMAX];

int main()
{
    fin >> c >> d;
    --c, --d;
    if(c > d) swap(c, d);
    for(int i = 2; i <= c; ++i)
    {
        if(v[i][0]) continue; /// i nu este divizibil cu patratul unui nr prim
        a = 0, b = 0;
        if(v[i][1]) /// i nu este prim
        {
            for(int j = i; j <= d; j += i)
            {
                if(v[j][0]) v[j] = 0;
                else v[j] = 1;
                if(j <= c) ++a; /// Merg (i, j) si (j, i)
                else ++b; /// Merge doar (i, j)
            }
            sol -= a * (a + b);
        }
        else /// i este prim
        {
            for(int j = i; j <= d; j += i)
            {
                if(v[j][0]) v[j] = 2;
                else v[j] = 1;
                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;
}