Cod sursa(job #2951737)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 7 decembrie 2022 10:21:42
Problema Mins Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>
#define NMAX 2000003
using namespace std;

int x,y;

int ePatratPerfect[NMAX];//obs aici am 0 cand nu e pp si 1 altfel
int nrDivPrimi[NMAX];

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

int main()
{
    fin>>x>>y;
    x--;y--;
    int minim=min(x,y);//deci eu vreau numarul de numere prime intre ele din intervalul 0,min(x,y)
    long long int total=x*y;
    for(int i=2; i<=minim; i++)
    {
        if(nrDivPrimi[i]==0)
        {

             for (int k = 1;  1LL*k * i <= 1LL*minim; k++) {
                nrDivPrimi[i * k]++;
            }
            for (int k = 1;  1LL*k * i * i <= 1LL*minim; k++) {
                ePatratPerfect[k * i * i] = 1;//setez ca nu e pp
            }

        }

        if(ePatratPerfect[i]==0)
        {
            long long val=1LL*(x/i)*(y/i);
            if(nrDivPrimi[i]%2==1)
            {
                total-=val;
            }
            else{
                total+=val;
            }
        }
    }
    fout<<total;
    return 0;
}