Cod sursa(job #635051)

Utilizator deneoAdrian Craciun deneo Data 18 noiembrie 2011 12:03:15
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define unusable -100000

int n, m;
int d[1000001];
long long sol;

int main ()
{
    int i, j, minim = 0;
	freopen ("mins.in", "r", stdin);
	freopen ("mins.out", "w", stdout);

	scanf ("%d %d", &n, &m);
	n--;m--;

    minim = min(n, m);
    for(i = 2; i <= minim; ++i)
        if(d[i] == 0)
        {
            for(j = i * i; j <= minim; j += i * i)
                d[j] = unusable;
            for(j = i; j <= minim; j += i)
                ++d[j];
        }
    for (i = 2; i <= minim; i ++)
		if (d[i] > 0)
        {
			if (d[i] & 1)
				sol -= (long long)(n / i) * (m / i);
			else
				sol += (long long)(n / i) * (m / i);
        }
    printf("%lld", sol +  (long long)n * m);
    return 0;
}