#include <bits/stdc++.h>
using namespace std;

ifstream fi("light2.in");
ofstream fo("light2.out");

using i64 = long long;

map<int, int> mp;
vector<int> nums;
i64 ant, n;
int k;

static i64 gcd(i64 a, i64 b) {
	i64 t;
	while (b > 0) {
		a%= b;
		swap(a, b); }
	return a; }

static i64 lcm(i64 a, i64 b) {
	return a / gcd(a, b) * b; }

static void bkt(int p, int taken, i64 lcm_now) {
	if (lcm_now > n) return;
	if (p == k) {
		if (taken)
			ant+= (taken % 2 ? 1 : -1) * (1 << taken - 1) * (n / lcm_now); // an incredible case of a good overflow
		return; }
	bkt(p + 1, taken + 1, lcm(lcm_now, nums[p]));
	bkt(p + 1, taken, lcm_now); }

int main() {
	fi >> n >> k;
	for (int t, i = 0; i < k; ++i)
		fi >> t, mp[t]++;

	for (auto i: mp)
		if (i.second % 2)
			nums.push_back(i.first);
	k = nums.size();
	bkt(0, 0, 1);

	fo << ant << endl;

	return 0; }