Cod sursa(job #2849362)

Utilizator db_123Balaban David db_123 Data 14 februarie 2022 23:15:50
Problema Mins Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <bitset>

using namespace std;

#define ll long long int

ifstream cin("mins.in");
ofstream cout("mins.out");

const int DIM = 1e6+1;

int  ciur[DIM];
bitset<1> valid[DIM]={0};
int C, D;

int main()
{

    cin >> C >> D;
    C--; D--;

    int minCD = min(C, D);
    ll sol = 1LL * C * D;                   /// total puncte

    for(int i = 2;i <= minCD;i++ )
    {
        if(ciur[i] > 0)
            continue;                       /// neprim continua

        for (int j = i;j <= minCD; j += i ) /// ciur
            ciur[j]++;

        if(1LL * i * i <= minCD )           /// sqrt prime factor ciur
            for (int j = i*i;j <= minCD;j += i*i)
                valid[j] = 1;
    }

    for ( int i = 2; i <= minCD;i++){
        if(valid[i] == 0){
            if(ciur[i] !=0)
                sol -= 1LL*(C/i)*(D/i);
            else
                sol += 1LL*(C/i)*(D/i);
        }
    }
    cout<<sol;

    return 0;
}