Cod sursa(job #631066)

Utilizator ChallengeMurtaza Alexandru Challenge Data 6 noiembrie 2011 21:12:35
Problema Mins Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include <fstream>

using namespace std;

const char InFile[]="mins.in";
const char OutFile[]="mins.out";
const int MaxM=1000111;

ifstream fin(InFile);
ofstream fout(OutFile);

long long c,d,sol;
int M,P[MaxM];
char D[MaxM];

int main()
{
	fin>>c>>d;
	fin.close();

	M=max(c,d);
	for(register int i=2;i<M;++i)
	{
		if(!P[i])
		{
			for(register int j=i;j<M;j+=i)
			{
				++P[j];
				if((j/i)%i==0)
				{
					D[j]=1;
				}
			}
		}
	}

	--c;--d;
	sol=c*d;
	for(register int i=2;i<M;++i)
	{
		if(!D[i])
		{
			if(P[i]&1)
			{
				sol-=(c/i)*(d/i);
			}
			else
			{
				sol+=(c/i)*(d/i);
			}
		}
	}

	fout<<sol;
	fout.close();
	return 0;
}