#include <fstream>
#include <iostream>
using namespace std;

#include <stdio.h>
#include <time.h>
#include <string.h>

// Размер окна биткарты в байтах
#define BM_SIZE 8192 // 8 Kb

int main(int argc, char**argv)
{
	// Считывание задания
	ifstream in("input.txt");
	int N, K;
	in >> N >> K;
	bool P[51] = { 0 };
	int cnt = 0; // кол-во полезных счетчиков
	for (int i = 0; i < K; i++) {
		int v;
		in >> v;
		P[v] = !P[v];
		if (P[v]) {
			cnt++;
		} else {
			cnt--;
		}
	}
	if (P[1]) cnt--; // единицы не считаем

	int res = 0;
	if (cnt) {
		int* steps = (int*)calloc(cnt, sizeof(int)); // шаги счетчиков
		int* values = (int*)calloc(cnt, sizeof(int)); // значения счетчиков
		for (int i = 2, j = 0; i <= 50; i++) {
			if (P[i]) {
				if(i <= 25 && P[i * 2]) {
					// Объединение счетчиков с шагом отличающимся вдвое
					steps[j] = i * 2;
					values[j] = i;
					P[i * 2] = false;
					cnt--;
				} else {
					steps[j] = i;
					values[j] = i;
				}
				j++;
#ifdef _DEBUG
				cout << steps[j - 1] << " ";
#endif
			}
		}
		// Для подсчета единичных бит в байте
		int bit_cnt[256] = { 0 };
		for (int i = 0; i < 256; i++) {
			int n = i;
			while (n != 0) {
				bit_cnt[i]++;
				n &= (n - 1);
			}
		}
		// Биткарта
		unsigned char* bm = (unsigned char*)calloc(BM_SIZE, 1);
		int next = 0;
		//int cnt_bad = 0;
		while (next <= N) {
			int start = next;
			next += BM_SIZE * 8;
			if (next > N) next = N + 1;
			// Заполнение окна биткарты
			for (int i = 0; i < cnt; i++) {
				int lim = next - start; // конец биткарты
				register int v = values[i] - start, s = steps[i];
				for (; v < lim; v += s) {
					//if ((bm[v >> 3] & (1 << (v & 7))) != 0) cnt_bad++;
					bm[v >> 3] ^= (1 << (v & 7));
				}
				values[i] = v + start;
			}
			// считывание результата
			for (int i = 0; i < BM_SIZE; i += 4) {
				register unsigned int k = *((int*)&bm[i]);
				res += bit_cnt[k & 0xFF];
				res += bit_cnt[(k >> 8) & 0xFF];
				res += bit_cnt[(k >> 16) & 0xFF];
				res += bit_cnt[k >> 24];
				*((int*)&bm[i]) = 0;
			}
		}
		//cout << "cnt_bad " << cnt_bad << endl;
	}
	// Инверсия если была единица
	if (P[1]) res = N - res;
	// Вывод результата
	ofstream out("output.txt");
	out << res << endl;
	out.close();
	cout << endl << "time " << clock() << endl;
	cout << "Result " << res << endl;
	return 0;
}

1000000000 32
1 2 3 5 7 9 11 13 15 17 19 23 25 27 28 29 31 32 33 45 36 37 39 40 41 42 43 44 45 47 48 49

1000000000 16
2 3 5 7 11 13 17 19 23 29 31 37 39 41 43 47