Cod sursa(job #379769)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 3 ianuarie 2010 21:10:27
Problema Mins Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include<stdio.h>
#include<vector>
#define N 1000000
using namespace std;
int c,d,p,nr,ind;
int x;
int v[N+2][8];

void read()
{
	freopen("mins.in","r",stdin);
	freopen("mins.out","w",stdout);
	scanf("%d%d",&c,&d);
	c--;
	d--;
}

void ciur()
{
	int i,j;
	for(i=2;i<=1<<18;i++)
		if(v[i][0]==0)
		{
			for(j=i;j<=1<<18;j+=i)
			{
				v[j][++v[j][0]]=i;
			}
		}
}

void back(int k)
{
	if(p>c || p>d)
		return;
	if(k==1+v[ind][0])
	{
		if(nr&1)
			x-=d/p;
		else
			x+=d/p;
		return;
	}
	back(k+1);
	p=p*v[ind][k];
	nr++;
	back(k+1);
	nr--;
	p=p/v[ind][k];
}

void rez()
{
	int i;
	long long sol=d;
	for(i=2;i<=c;i++)
	{
		x=0;
		p=1;
		ind=i;
		nr=0;
		back(1);
		sol+=x;
	}
	printf("%lld\n",sol);
}

int main()
{
	read();
	ciur();
	rez();
	return 0;
}