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

#include <stdio.h>
#include <time.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]) {
				steps[j] = i;
				values[j] = i;
				j++;
#ifdef _DEBUG
				cout << i << " ";
#endif
			}
		}
		// Для подсчета единичных бит в байте
		int bit_cnt[256] = { 0 };
		for (int i = 0; i < 256; i++) {
			int n = i;
			while (n != 0) {
				bit_cnt[i]++;
				n = n & (n - 1);
			}
		}
		// Биткарта
		unsigned char* bm = (unsigned char*)calloc(BM_SIZE, 1);
		int next = 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; // конец биткарты
				int v = values[i] - start, s = steps[i];
				for (; v < lim; v += s) { 
					bm[v >> 3] ^= (1 << (v & 7));
				}
				values[i] = v + start;
			}
			// считывание результата
			for (int i = 0; i < BM_SIZE; i++) {
				res += bit_cnt[bm[i]];
				bm[i] = 0;
			}
		}
	}
	// Инверсия если была единица
	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 50
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 45 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

1000000000 25
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50

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

#include <stdio.h>
#include <time.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 << i << " ";
#endif
			}
		}
		// Для подсчета единичных бит в байте
		int bit_cnt[256] = { 0 };
		for (int i = 0; i < 256; i++) {
			int n = i;
			while (n != 0) {
				bit_cnt[i]++;
				n = n & (n - 1);
			}
		}
		// Биткарта
		unsigned char* bm = (unsigned char*)calloc(BM_SIZE, 1);
		int next = 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; // конец биткарты
				int v = values[i] - start, s = steps[i];
				for (; v < lim; v += s) {
					bm[v >> 3] ^= (1 << (v & 7));
				}
				values[i] = v + start;
			}
			// считывание результата
			for (int i = 0; i < BM_SIZE; i++) {
				res += bit_cnt[bm[i]];
				bm[i] = 0;
			}
		}
	}
	// Инверсия если была единица
	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;
}