Cod sursa(job #1982574)

Utilizator eilerGabriel-Ciprian Stanciu eiler Data 19 mai 2017 14:30:30
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.64 kb
#include <fstream>
using namespace std;

int c, d, fp[1000001];
bool cm[1000001], np[1000001];

int main(){
	int c, d, x, i, j;
	long long k, r;

	ifstream fin ("mins.in");
	fin >> c >> d;
	c--; d--;
	fin.close();

	x=min(c, d);
	cm[0]=cm[1]=true;
	for (i=2; i<=x; i++)
		if (cm[i]==false){
			for (k=i*i; k<=x; k+=i*i)
				np[k]=true;
			for (j=2; i*j<=x; j++){
				fp[i*j]++;
				cm[i*j]=true;
			}
		}

	r=c*d;
	for (i=2; i<=x; i++)
		if (np[i]==false){
				if (fp[i]%2==0)
					r-=(c/i)*(d/i);
				else
					r+=(c/i)*(d/i);
		}

	ofstream fout ("mins.out");
	fout << r << '\n';
	fout.close();

	return 0;
}