Cod sursa(job #2097569)

Utilizator zhm248Mustatea Radu zhm248 Data 31 decembrie 2017 19:53:58
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include<cstdio>
#include<cmath>
using namespace std;
int v[1000001],c,d,lim;
long long sol=0;
void psciur(int x)
{
    int lim=(int)sqrt(x);
    for(int i=2; i<=x; ++i)
    {
        if(v[i]>=0)
        {
            if(v[i]%2)
                sol-=(((1LL*c)/(1LL*i))*((1LL*d)/(1LL*i)));
            else
                sol+=(((1LL*c)/(1LL*i))*((1LL*d)/(1LL*i)));
            if(!v[i])
            {
                for(int j=i; j<=x; j+=i)
                {
                    if(v[j]>=0)
                        v[j]++;
                }
            }
            if(i<=lim)
            {
                for(int j=i*i; j<=x; j+=i*i)
                {
                    v[j]=-1;
                }
            }
        }
    }
}

int main()
{
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    int minim;
    scanf("%d%d",&c,&d);
    c--;
    d--;
    if(c<=d)
        minim=c;
    else
        minim=d;
    psciur(minim);
    printf("%lld\n",1LL*c*d-sol);
    return 0;
}