Cod sursa(job #635258)

Utilizator sebii_cSebastian Claici sebii_c Data 19 noiembrie 2011 00:53:37
Problema Mins Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <stdio.h>
#define NMAX 2000010

long long result, nd, n, m;
long long div[NMAX];
char sieve[NMAX];

void back(long long nr, long long k, long long pos)
{
	long long i;
	long long x;
	long long c = (long long) (n / nr) * (m / nr);

	if (k % 2 == 1)
		result -= c;
	else
		result += c;

	for (i = pos; i <= nd; ++i) {
		x = nr * div[i];
		if (x <= n) 
			back(nr * div[i], k + 1, i + 1);
		else
			return;
	}
}	

int main()
{
	freopen("mins.in", "r", stdin);
	freopen("mins.out", "w", stdout);
	long long i, j;
	scanf("%lld %lld", &n, &m);
	if (n > m) {
		result = m;
		m = n;
		n = result;
	}
	--n; --m;
	result = 0;
	
	nd = 0;
	for (i = 2; i <= m; ++i)
		if (!sieve[i]) {
			div[++nd] = i;
			if (i * i <= m)
				for (j = i * i; j <= m; j += i)
					sieve[j] = 1;
		}

	result = 0;
	back(1, 0, 1);
	printf("%lld\n", result);
	
	return 0;
}