Cod sursa(job #1416770)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 8 aprilie 2015 22:00:50
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <cstdio>
#include <algorithm>

#define Nmax 1000010

using namespace std;

int c , d , i , j;

long long drepte;

bool ciur[Nmax] , no[Nmax] , D[Nmax];

int main()
{
    freopen("mins.in","r",stdin);
    freopen("mins.out","w",stdout);

    scanf("%d %d", &c, &d);

    if (c > d) swap(c , d); c--; d--;

    drepte = 1LL * c * d;

    for (i = 2; i <= c; ++i)
    {
        if (!ciur[i])
        {
            for (j = i; j <= c; j += i)
                ciur[j] = 1 , D[j] ^= 1;

            for (j = i * i; j <= c && 1LL * i * i <= 1LL * c; j += i * i)
                no[j] = 1;
        }

        if (!no[i])
        {
            if (D[i]) drepte -= 1LL * (c / i) * (d / i);
            else drepte += 1LL * (c / i) * (d / i);
        }
    }

    printf("%lld\n", drepte);

    return 0;
}