Cod sursa(job #541661)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 25 februarie 2011 13:04:08
Problema Light2 Scor 80
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 1 Marime 0.82 kb
#include <cstdio>

typedef long long LL;

const int KMAX=22;

LL N,ret_lcm[1<<KMAX],nr[1<<KMAX];
int K,d[KMAX],hash[37];

LL gcd(LL x, LL y) { return y != 0 ? gcd(y,x%y) : x; }
LL lcm(LL x, LL y)
{ 
	if (x>N || y>N) return N+1;
	x = x/gcd(x, y);
	if (x > N/y) return N+1;
	return x*y;
}


int main()
{
	freopen("light2.in","r",stdin);
	scanf("%lld",&N);
	scanf("%d",&K);
	for (int i=0;i<K;++i) scanf("%d", &d[i]);

	for (int i=0;i<K;++i) hash[(1<<i)%37] = i;

	int pow2k = 1<<K;
	ret_lcm[0]=1;

	LL ans=0;

	for (int i=1;i<pow2k;++i)
	{
		int j = i&(i-1);
		ret_lcm[i] = lcm( ret_lcm[j], d[hash[(i-j)%37]]);
		nr[i] = nr[j]+1;
		LL tmp = (N/ret_lcm[i])*(1LL << (nr[i]-1));
		if (nr[i]&1) ans+=tmp;
			    else ans-=tmp;
	}

	freopen("light2.out","w",stdout);
	printf("%lld\n", ans);

	return 0;
}