#include <fstream>
#include <queue>

using namespace std;

typedef long long int64;

int64 N, K;
int D[24];
int64 result;
int64 Comb[24][24], C[24][24];
char nrb[1 << 22], log[1 << 22];
int64 val[1 << 20];

inline int64 cmmdc(int64 a, int64 b)
{
	if (b == 0) return a;
	return cmmdc(b, a % b);
}

int main()
{
	ifstream fin("light2.in");
	ofstream fout("light2.out");
	
	for (int i = 1; i < (1 << 22); ++i)
	{
		nrb[i] = nrb[i & (i - 1)] + 1;
		if (i >= 2) log[i] = log[i >> 1] + 1;
	}
	
	Comb[0][0] = 1;
	for (int i = 1; i <= 22; ++i)
	{
		Comb[i][0] = 1;
		for (int j = 1; j <= i; ++j)
		{
			Comb[i][j] = Comb[i - 1][j] + Comb[i - 1][j - 1];
			C[i][j] = C[i][j - 1] + Comb[i][j] * (-C[j][j - 1] + j % 2);
		}
	}
	
	fin >> N >> K;
	for (int i = 1; i <= K; ++i)
		fin >> D[i];
	
	val[0] = 1;
	for (int i = 1; i < (1 << K); ++i)
	{	
		int now = i;
		int64 value = 1, cmm = 1;
		
		for (char j = K - 1; j >= 0 && now >= (1 << 20); --j)
			if (i & (1 << j))
			{
				now ^= (1 << j);
				cmm = cmm * cmmdc(value, D[j + 1]);
				value = value  * D[j + 1];
			}
		value = value / cmm;
		if (value > N) value = 0;
		
		if (now == i)
		{
			value = D[log[now & -now] + 1];
			now &= now - 1;
		}
		
		value = value / cmmdc(value, val[now]) * val[now];
		if (value > N || value == 0)
		{
			if (i < (1 << 20))
				val[i] = 0;
			continue;
		}
		
		if (i < (1 << 20))
			val[i] = value;
		
		result += (-C[nrb[i]][nrb[i] - 1] + nrb[i] % 2) * (N / value);
	}
	
	fout << result;
	
	fin.close();
	fout.close();
}