Cod sursa(job #591878)

Utilizator celmaicontcont de cont celmaicont Data 25 mai 2011 19:43:40
Problema Mins Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.72 kb
#include <algorithm>
#include <stdio.h>

#define MAX 1000010
#define ll long long

using namespace std;

int dp[MAX], prim[MAX];
int n, m;
ll sol;

int main()
{
	freopen("mins.in", "r", stdin);
	freopen("mins.out", "w", stdout);
	
	scanf("%d %d", &n, &m);
	n--, m--;
	if (n > m)
		swap(n, m);

	for (int i = 2; i <= n; i++)
	{
		if (!prim[i])
		{
			for (int j = i; j <= n; j += i)
			{
				prim[j] = 1;
				dp[j]++;
			}

			for (ll j = i * i; j <= n; j += (ll) i * i)
				dp[j] = -LONG_MAX;
		}
		if (dp[i] > 0)
		{
			int im = m / i;
			if (!(dp[i] & 1))
				im *= -im;
			sol += (im * (n / i));
		}
	}

	printf("%lld\n", (ll) n * m - sol);

	fclose(stdin);
	fclose(stdout);
	return 0;
}