Cod sursa(job #591915)

Utilizator celmaicontcont de cont celmaicont Data 25 mai 2011 20:50:01
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.78 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);

	ll sol = (ll) n * m;
	for (int i = 2; i <= n; i++)
	{
		if (!prim[i])
		{
			for (int j = i; j <= n; j += i)
			{
				prim[j] = 1;
				if (dp[j] >= 0)
					dp[j]++;
			}

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

	printf("%lld\n", sol);

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