Cod sursa(job #700172)

Utilizator elfusFlorin Chirica elfus Data 1 martie 2012 00:43:05
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>

int c[1000100], blocked[1000100];

int main ()
{
    int N, M, mi, i, j;
    long long sol;

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

    scanf ("%d%d", &N, &M);
    N --; M --;
    sol = (long long)N * M;
    mi = N < M ? N : M;

    for (i = 2; i <= mi; i ++)
        if (c[i] == 0)
        {
            for (j = i; j <= mi; j += i)
                c[j] ++;
            for (j = i * i; j <= mi; j = j + i * i)
                blocked[j] = 1;
        }

    for (i = 2; i <= mi; i ++)
        if (!blocked[i])
            if (c[i] % 2 == 1)
                sol = sol - (long long)(N / i) * (M / i);
            else
                sol = sol + (long long)(N / i) * (M / i);

    printf ("%lld", sol);
    return 0;
}