Cod sursa(job #3326458)

Utilizator raulthestormIlie Raul Ionut raulthestorm Data 29 noiembrie 2025 08:41:36
Problema Mins Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <fstream>

using namespace std;
const int MAX = 5001;

int ciurn[MAX], ///Vector al numarului de divizori primi
    ciurp[MAX], ///Ciurul numerelor divizibile cu patrate de numere prime
    c, d, n;    ///(i.e. la care nu toti divizorii primi sunt distincti)
long long card;

ifstream f("mins.in");
ofstream g("mins.out");

void calcul(int i)
{
	if(ciurn[i] == 0)
	{
		for(int j = i; j <= n; j += i)
			ciurn[j]++;
		int k = i * i;
		for(int jj = k; jj <= n; jj += k)
			ciurp[jj] = 1;
	}
	if(ciurp[i] == 0)
	{
		int t = (c / i) * (d / i);
		if(ciurn[i] % 2 == 0)
			card -= t;
		else
			card += t;
	}
}

int main()
{
	f >> c >> d;
	c--, d--;
	n = min(c, d);
	for(int i = 2; i <= n; i ++)
		calcul(i);
	g << 1LL * c * d - card;
	f.close();
	g.close();
	return 0;
}