Cod sursa(job #394406)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 10 februarie 2010 20:22:55
Problema Mins Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <stdio.h>
#define NMAX 10
#define ll long long
int a,b,div[NMAX],r,sum,ap[NMAX],nr;
ll rez;
void desc(int x)
{
	int 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;
}
int main()
{
	freopen("mins.in","r",stdin);
	freopen("mins.out","w",stdout);
	scanf("%d%d",&a,&b);
	int i;
	a--; b--;
	for (i=1; i<=a; i++)
		rez+=pr(i);
	printf("%lld\n",rez);
	return 0;
}