Cod sursa(job #1849590)

Utilizator zdavid112zIon David-Gabriel zdavid112z Data 17 ianuarie 2017 18:25:59
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <cstdio>
#include <algorithm>

using namespace std;

int c, d, n;
int v[1000010];
int vp[1000010];

void ciur()
{
    int i, j;
    for(i = 2; i <= n; i += 2) {
        v[i] = 1;
    }
    for(i = 4; i <= n; i += 4) {
        vp[i] = 1;
    }
    for(i = 3; i <= n; i += 2)
    {
        if(v[i] == 0)
        {
            for(j = i; j <= n; j += i)
                v[j]++;
            if(1LL * i * i <= n)
                for(j = i * i; j <= n; j += i * i)
                    vp[j] = 1;
        }
    }
}

int main()
{
    long long rez = 0;
    int i, j;
    freopen("mins.in", "r", stdin);
    freopen("mins.out", "w", stdout);
    scanf("%d%d", &c, &d);
    c--; d--;
    n = min(c, d);
    ciur();

    for(i = 2; i <= n; i++)
    {
        if(vp[i] == 0)
        {
            if(v[i] & 1)
                rez += 1LL * (c / i) *  (d / i);
            else rez -= 1LL * (c / i) *  (d / i);
        }
    }
    printf("%lld", 1LL * c * d - rez);
    return 0;
}