#include <cstdio>
#include <vector>

using namespace std;

const int maxK = 23;

long long N;
int K;
int badT[maxK];
vector <int> T;
int comb[maxK][maxK];
int coef[maxK];
int p2[maxK];
long long sol;
int st[maxK];
//long long prod[1 << 20];

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

	return b;
}

inline void back(int k, long long prod, int nBiti) {
	int i;
	if (k == K) {
		if (nBiti == 0)
			return;

		int sgn = 1;
		if (nBiti % 2 == 0)
			sgn = -1;

		nBiti--;
		sol += (1LL * sgn * p2[nBiti] * (N / prod));
		return;
	}

	for (i = 0; i < 2; i++) {
		st[k + 1] = i;
		if (i == 0) 
			back(k + 1, prod, nBiti);
		else {
			long long cd = cmmdc(prod, 1LL * T[k]);
			back(k + 1, prod * T[k] / cd, nBiti + 1);
		}
	}
}

int main() {
	int i, j;
	freopen("light2.in", "r", stdin);
	freopen("light2.out", "w", stdout);

	scanf("%lld", &N);
	scanf("%d", &K);
	for (i = 1; i <= K; i++) 
		scanf("%d", &badT[i]);

	comb[0][0] = 1;
	for (i = 1; i <= K; i++) {
		comb[i][0] = 1;
		for (j = 1; j <= i; j++)
			comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1];
	}


	for (i = 1; i <= K; i++) {
		bool ok = 1;
		for (j = 1; j < i; j++)
			if (badT[j] == badT[i])
				ok = 0;
		
		if (ok == 0)
			continue;

		int nr = 0;
		for (j = 1; j <= K; j++)
			if (badT[i] == badT[j])
				nr++;

		if (nr % 2 == 1)
			T.push_back(badT[i]);
	}

	for (i = 0; i <= K; i++)
		p2[i] = (1 << i);

	K = T.size();

	sol = 0;

	back(0, 1, 0);

	printf("%lld\n", sol);

	return 0;
}