Cod sursa(job #388015)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 29 ianuarie 2010 08:34:52
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include <iostream>
#include <cstdlib>
#include <bitset>
#include <vector>

using namespace std;

#define	maxN		1000100
#define pb		push_back
#define bit(i, x)	(((i) >> x) & 1)

int N, M, mx;
long long Sol = 2;
bitset< maxN > Prime;
vector<int> Primes;

void get_divs( ) {
	int i, j, maxI = max(N, M);
	Prime.set(); Prime[0] = Prime[1] = false;
	
	for (i = 4; i <= maxI; i += 2)
		Prime[i] = false;
	Primes.push_back(2);	
	
	for (i = 3; i <= maxI; i += 2)
		if (Prime[i]) {
			Primes.push_back(i);
			for (j = i + i; j <= maxI; j += i)
				Prime[j] = false;
		}
}

void backtrk(int P, int X, int Val, int Nr) {
	if (P == X || 1LL * Val * Primes[P] > 1LL * mx) {
		if (Nr % 2 == 0)
			Sol += 1LL * (M / Val) * (N / Val);
		else	Sol -= 1LL * (M / Val) * (N / Val);
		return;
	}
	backtrk(P + 1, X, Val, Nr);
	backtrk(P + 1, X, Val * Primes[P], Nr + 1);
}

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

	scanf("%d%d", &N, &M);
	if (N == 1 && M == 1) {
		printf("0\n");
		return 0;
	}
	if (N == 1 || M == 1) {
		printf("1\n");
		return 0;
	}
	get_divs(); M --; N --; mx = (N < M) ? N : M;
	backtrk(0, Primes.size(), 1, 0);
	cout << Sol - 2<< "\n";
	
}