Cod sursa(job #394410)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 10 februarie 2010 20:28:44
Problema Mins Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <stdio.h>
#define NMAX 10
#define ll long long
int a,b,div[NMAX],r,sum,ap[NMAX],nr,A[NMAX];
ll rez;
void desc(int x)
{
	int i;
	for (i=1; i<=8; i++)
		if (x%A[i]==0)
		{
			div[++r]=A[i];
			while (x%A[i]==0)
				x/=A[i];
		}
	for (i=2; i*i<=x; i++)
		if (x%i==0)
		{
			div[++r]=i;
			while (x%i==0)
				x/=i;
		}
	if (x!=1)
		div[++r]=x;
}
void act(int k)
{
	if (k & 1)
		sum+=b/nr;
	else
		sum-=b/nr;
}
void back(int k)
{
	if (k==r+1)
		return ;
	int i;
	for (i=ap[k-1]+1; i<=r; i++)
	{
		ap[k]=i;
		nr*=div[i];
		act(k);
		back(k+1);
		nr/=div[i];
	}
}
int pr(int x)
{
	r=0; sum=0; nr=1;
	desc(x);
	back(1);
	return b-sum;
}
void precompute()
{
	A[1]=2; A[2]=3; A[3]=5; A[4]=7; A[5]=11; A[6]=13; A[7]=17; A[8]=19;
}
int main()
{
	freopen("mins.in","r",stdin);
	freopen("mins.out","w",stdout);
	scanf("%d%d",&a,&b);
	int i,t;
	precompute();
	a--; b--;
	if (a>b)
		t=a,a=b,b=t;
	for (i=1; i<=a; i++)
		rez+=pr(i);
	printf("%lld\n",rez);
	return 0;
}