Cod sursa(job #631096)

Utilizator KoniacDocea Andrei Koniac Data 6 noiembrie 2011 22:23:43
Problema Mins Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<fstream>
using namespace std;

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

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

long long c,d,sol;
int M,p[lim];
char w[lim];


int main() {
	fin>>c>>d;
	fin.close();
	c--;
	d--;
	int mins=min(c,d);
	for(register int i=2;i<=mins;++i)
		if(w[i]==0){
			p[i]++;
			long long ii=i*i;
			for(register int j=2*i;j<=mins;j+=i){
				w[j]=1;
				if(j%ii)
					p[j]++;
			}
		}
	
	for(register int i=2;i<=1000;++i)
		if(!w[i]){
			int ii=i*i;
			for(register int j=ii;j<=mins;j+=ii)
				p[j]=0;
				
		}
		
	for(register int i=1;i<=mins;++i)
		if(p[i])
			if(p[i]%2)
				sol+=(c/i)*(d/i);
			else
				sol-=(c/i)*(d/i);
			
	long long a=c*d;
	fout<<a-sol;
	fout.close();
	return 0;
}