Cod sursa(job #699203)

Utilizator elfusFlorin Chirica elfus Data 29 februarie 2012 18:10:02
Problema Mins Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
//JOS ACTA!

#include <stdio.h>

int x[1000], f[100];

inline bool isPrime (int x)
{
	int d;
	
	for (d = 3; d * d <= x; d = d + 2)
		if (x % d == 0)
			return 0;
	return 1;
}

int main ()
{
	int c, d, i, j, ci, sol = 0, b, now, ter, now2;
	
	freopen ("mins.in", "r", stdin);
	freopen ("mins.out", "w", stdout);

	scanf ("%d%d", &c, &d);
	
	x[++ x[0]] = 2;
	for (i = 3; i <= d; i ++)
		if (isPrime (i))
			x[++ x[0]] = i;
	for (i = 1; i <= c; i ++)
	{
		ci = i;
		f[0] = 0;
		for (j = 1; x[j] * x[j] <= ci; j ++)
			if (ci % x[j] == 0)
			{
				f[++ f[0]] = j;
				while (ci % x[j] == 0)
					ci = ci / x[j];
			}
		if (ci > 1)
			f[++ f[0]] = ci;
		now2 = 0;
		for (j = 1; j < (1 << f[0]); j ++)
		{
			now = 1; ter = 0;
			for (b = 0; b < f[0]; b ++)
				if (j & (1 << b))
					now = now * f[b + 1], ter ++;
			if (ter & 1)
				now2 = now2 + d / now;
			else
				now2 = now2 - d / now;
		}
		sol = sol + now2;
	}
	
	printf ("%d", sol);
	return 0;
}
 
//jos actaaaaaaaaaaaaaaaa!!!! sa ma p*s pe el de tratat