Cod sursa(job #1415768)

Utilizator VAIonescuIonescu Vlad-Andrei VAIonescu Data 6 aprilie 2015 07:36:52
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX=1000000;

int ciur[MAX+1];
bool put[MAX+1];
int c,d;

int main()
{
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);
    scanf("%d%d", &c, &d);
    c--;
    d--;
    int lmax=min(c,d);
    int i,j;
    long long sol=1LL*c*d;

    for (i=2;i<=lmax;++i)
    {
        if(!ciur[i])
        {
            for (j=i;j<=lmax;j+=i)
                ciur[j]++;
            if (1LL*i*i<=lmax)
                for (j=i*i;j<=lmax;j+=i*i)
                    put[j]=true;
        }
    }
    for (i=2;i<=lmax;++i)
        if (put[i]==false)
        {
            if (ciur[i]%2)
                sol-=1LL*(c/i)*(d/i);
            else
                sol+=1LL*(c/i)*(d/i);
        }
    printf("%lld", sol);
    return 0;
}