Cod sursa(job #635243)

Utilizator sebii_cSebastian Claici sebii_c Data 18 noiembrie 2011 22:37:55
Problema Mins Scor 0
Compilator c Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <stdio.h>
#define NMAX 2000010

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

inline long long min(long long a, long long b)
{
	return (a < b) ? a : b;
}

inline long long max(long long a, long long b)
{
	return (a > b) ? a : b;
}

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(x, k + 1, i);
		else
			return;
	}
}	

int main()
{
	freopen("mins.in", "r", stdin);
	freopen("mins.out", "w", stdout);
	long long c, d;
	long long i, j;
	scanf("%lld %lld", &c, &d);
	n = min(c, d);
	m = max(c, d);
	--n; --m;
	
	sieve[0] = sieve[1] = 1;
	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;
}