Cod sursa(job #474128)

Utilizator darrenRares Buhai darren Data 2 august 2010 16:18:43
Problema Mins Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>

using namespace std;

ifstream fin("mins.in");
ofstream fout("mins.out");

void PreGen();
void Read();
void Solve();
int NumP(int x);
void Fact(int x);
void Write();

int n, m, sp, sf;
int prim[100], fac[20];
bool pr[1000];
long long wrong;

int main()
{
	PreGen();
	Read();
	if (n <= 5000 && m <= 5000)
	{
		Solve();
		Write();
	}
	else fout << -1;
}

void PreGen()
{
	prim[++sp] = 2;
	for (int i  = 3; i <= 1000; i += 2)
		if (pr[i] == false)
		{
			prim[++sp] = i;
			for (int j = i * i; j <= 1000;  j += 2 * i)
				pr[j] = true;
		}
}

void Read()
{
	fin >> n >> m;
}

void Solve()
{
	for (int i = 1; i < n; ++i)
		wrong += NumP(i);
}

int NumP(int x)
{
	sf = 0;
	Fact(x);

	int prod, what;
	int result = 0;

	for (int i = 1; i < (1 << sf); ++i)
	{
		prod = 1;
		for (int j = 0; j < sf; ++j)
			if (((1 << j) & i) != 0)
				prod *= fac[j + 1];
		what = (m - 1) / prod;

		int np = 0, aux = i;
		while (aux)
		{
			++np;
			aux &= aux - 1;
		}

		if (np % 2 == 1) result += what;
		else             result -= what;
	}

	return result;
}

void Fact(int x)
{
	for (int i = 1; i <= sp; ++i)
		if (x % prim[i] == 0)
		{
			fac[++sf] = prim[i];
			while (x % prim[i] == 0)
				x /= prim[i];
		}
	if (x != 1)
		fac[++sf] = x;
}

void Write()
{
	fout << (n - 1) * (m - 1) - wrong;
}