Cod sursa(job #265904)

Utilizator savimSerban Andrei Stan savim Data 24 februarie 2009 18:53:20
Problema Fractii Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <stdio.h>
#define LL unsigned long long

#define MAX_P 1000010

LL n, m, i;
LL prim[MAX_P / 10];
LL sol;

bool ciur[MAX_P], fol[MAX_P];

void calc_prim() {
	for (i = 2; i < MAX_P; i++)
		if (ciur[i] == 0) {
			prim[++prim[0]] = i;
			for (int j = i; j < MAX_P; j += i)
				ciur[j] = 1;
	    }
}

void back(LL poz, LL fact, LL nr) {
	if (!fol[fact] && nr) {
		if (nr % 2 == 1) 
			sol += 1LL * (n / fact) * (m / fact);
		else sol -= 1LL * (n / fact) * (m / fact);
		fol[fact] = 1;
	}
	
	//folosesc divizorul prim[i]
	if (1LL * fact * prim[poz] < n) back(poz + 1, fact * prim[poz], nr + 1);
	else return;
	
	back(poz + 1, fact, nr);
}

int main() {

	#ifndef ONLINE_JUDGE
		freopen("data.in", "r", stdin);
		freopen("data.out", "w", stdout);
	#endif
	
	scanf("%lld", &n);
        n = m;
	
	calc_prim();
	
	n--; m--;
	back(1, 1, 0);
	
	if (!n) sol++;
	if (!m) sol++;
	printf("%lld\n", (LL) n * m + 2 - sol);
	
	return 0;
}