Cod sursa(job #2846302)

Utilizator marcumihaiMarcu Mihai marcumihai Data 9 februarie 2022 09:10:46
Problema Mins Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f ("mins.in");
ofstream g ("mins.out");

bool patrat[5000005];
short ciur[500005];
int c , d;



void eratostene()
{
    for(int i=2;i<=min(c , d);++i)
    {
        if(ciur[i]==0)
        {
            for(int j=i;j<=min(c , d);j+=i)
        {
            ciur[j]++;
        }
        for(int j=i*i;j<=min(c , d);j+=i*i)
            patrat[j]=1;
        }

    }
}


int main()
{
    f>>c>>d;
    long long rez=0;
    --c;
    --d;
    eratostene();
    for(int i=1;i<=min(c , d);++i)
    {
        if(patrat[i]==0)
        {
            if(ciur[i]%2==0)
                rez+=(c/i)*(d/i);
            else
                rez-=(c/i)*(d/i);

        }
    }
    g<<rez;




    return 0;
}