#include <cstdio>

#define Kmax 24

long long n, sol;
int k, d[Kmax], st[Kmax];

int euclid (long long a, long long b) {

	long long r = a % b;
	while (r) {
		a = b;
		b = r;
		r = a % b;
	}

	return b;
}

void back (int p, long long cmmdc, long long prod) {

	long long cmmmc;

	if (p > 2) cmmmc = prod / cmmdc;
	else cmmmc = cmmdc;

	if (cmmmc > n) return;

	if (p > 1) {
		if ((p-1)&1) sol+= n / cmmmc * ( 1 << (p-2) );
		else sol-= n / cmmmc * ( 1 << (p-2) );
	}

	if (p <= k) {
		for (int i = st[p-1] + 1; i <= k; i++) {
            st[p] = i;

            if (p == 1) back (p + 1, d[i], d[i]);
            else back (p + 1, euclid (cmmmc, d[i]), cmmmc * d[i]);
        }
	}
}

int main () {

	freopen ("light2.in", "r", stdin);
	freopen ("light2.out", "w", stdout);

	scanf ("%lld %d", &n, &k);
	for (int i = 1; i <= k; i++)
		scanf ("%d", &d[i]);

	back (1, 1, 1);

	printf ("%lld", sol);

	return 0;
}