Cod sursa(job #593851)

Utilizator maritimCristian Lambru maritim Data 4 iunie 2011 20:09:06
Problema Mins Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<stdio.h>

#define MaxN 1000001

int A[MaxN];
int Prim[5001];
bool B[MaxN];
int c;
int d;
unsigned long long MAX;
int MAX1;
int MIN1;
int nr;

inline int min(int a,int b)
{
	return a<b? a:b;
}

inline int max(int a,int b)
{
	return a>b? a:b;
}

int cmmdc(int a,int b)
{
	if(!b) return a;
	else return cmmdc(b,a%b);
}

int main()
{
	FILE *f = fopen("mins.in","r");
	FILE *g = fopen("mins.out","w");
	
	fscanf(f,"%d %d",&c,&d);
	MAX1 = max(c-1,d-1);
	MIN1 = min(c-1,d-1);
	MAX = 1;
	for(int i=2;i<=MAX1;i++)
		A[i] = min(i,MIN1);
	for(int i=2;i<=MIN1;i++)
		if(!B[i])
		{
			for(int j=i;j<=MAX1;j+=i)
			{
				A[j] -= min(j,MIN1)/i ;
				B[j] = true;
			}
			Prim[++nr] = i;
		}
	for(int i=1;i<=nr;i++)
		for(int j=i+1;j<=nr;j++)
			if(Prim[i]*Prim[j]<=MIN1)
				for(int k=Prim[i]*Prim[j];k<=MAX1;k+=Prim[i]*Prim[j])
					A[k] ++;
	for(int i=1;i<=MAX1;i++)
		if(i<=MIN1)
			MAX += 2*A[i];
		else
			MAX += A[i];
//	for(int i=1;i<=MAX1;i++)
//		printf("%d %d\n",i,A[i]);
	fprintf(g,"%d",MAX);
	
	fclose(g);
	fclose(f);
	return 0;
}