Cod sursa(job #526896)

Utilizator AndreyPAndrei Poenaru AndreyP Data 29 ianuarie 2011 18:54:04
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#include <bitset>
using namespace std;
#define ll long long
#define N 1000010

int c,d;
int n;
ll rez;
bitset< N > e,nr,sar;

inline void rezolva() {
	int j2;

	for(int i=2; i<=n; ++i) {
		if(!e[i]) {
			if(i<1001) {
				j2 = i*i;
                        	for(int j=j2; j<=n; j+=j2)
				       sar.set(j);
			}
			
			for(int j=i; j<=n; j+=i) {
				e.set(j);
				if(sar[j])
					continue;
				nr.flip(j);
			}
			e.reset(i);
		}

		if(sar[i])
			continue;

		if(nr[i])
			rez -= (ll)(c/i)*(ll)(d/i);
		else
			rez += (ll)(c/i)*(ll)(d/i);
	}
}

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

        scanf("%d%d",&c,&d);
	--c;
	--d;
	if(c<d)
		n = c;
	else
		n = d;
	rez = (ll)c*(ll)d;

	rezolva();
	printf("%lld\n",rez);

	return 0;
}