Исходный -> групповой
50->0
49->1
48->2
47->3
46->4
44->5
43->6
42->7
41->8
40->0
39->9
38->10
37->11
36->12
34->13
33->14
32->0
31->15
30->16
29->17
28->1
27->18
26->9
25->0
24->2
23->4
22->5
21->7
20->0
19->10
18->12
17->13
16->0
15->16
14->1
13->9
12->2
11->5
10->0
9->12
8->0
7->1
6->2
5->0
4->0
3->2
2->0
1->0
Слияние групповых
[18] => [2]
[17] => [12]
[16] => [0]
[15] => [5]
[14] => [7]
[13] => [10]
[12] => [2]
[11] => [4]
[10] => [9]
[9] => [0]
[8] => [6]
[7] => [1]
[6] => [3]
[5] => [1]
[4] => [2]

// http://acmp.ru/index.asp?main=task&id_task=337

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

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

//#define MAX_MEMORY 4194304 // 4 Мб
//#define MAX_MEMORY 8388608 // 8 Мб
#define MAX_MEMORY 14680064 // 14 Мб

// НОД
int64_t gcd(int64_t a, int64_t b) {
	return b ? gcd(b, a % b) : a;
}

// НОK
int64_t lcm(int64_t a, int64_t b) {
	return a / gcd(a, b) * b;
}

//Макс простой множитель
int max_prime(int n) {
	static int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
	if (n == 1) return 1;
	int* m = primes;
	while(n > 1) {
		if((n % *m) == 0) {
			n /= *m;
		} else {
			m++;
		}
	}
	return *m;
}

// Класс счетчика
class cnt_t {
	uint32_t* bm; // биткарта
	size_t size; // Размер в битах
	uint32_t* cur; // текущий элемент для перебора
	uint32_t* end; // конец bm
public:
	cnt_t() {
		bm = NULL;
	}

	~cnt_t() {
		if(bm != NULL) free(bm);
	}

	// Инициализация
	void init(int value) {
		size = lcm(value, 32);
		bm = (uint32_t*)calloc(size / 32, 4);
		cur = bm;
		end = bm + (size / 32);
		for (uint32_t i = 0; i != size; i += value) {
			bm[i >> 5] ^= (1 << (i & 31));
		}
	}

	// Склеивание с другим счетчиком
	bool clue(cnt_t& c) {
		size_t new_size = lcm(size, c.size);
		if(new_size > size) {
			uint32_t* bm_new = (uint32_t*) realloc(bm, new_size / 8);
			if (!bm_new) return false;
			bm = bm_new;
			cur = bm;
			end = bm + (size / 32);
			uint32_t* new_end = bm + (new_size / 32);
			for (uint32_t* p = end; p < new_end; p++) {
				*p = next();
			}
			size = new_size;
			cur = bm;
			end = new_end;
		}
		c.cur = c.bm;
		for (uint32_t* p = bm; p < end; p++) {
			*p ^= c.next();
		}
		return true;
	}

	// Склеивание с другим исходным счетчиком
	bool clue(int i) {
		if(add(i)) {
			return true;
		} else {
			cnt_t c;
			c.init(i);
			return clue(c);
		}
	}

	// Добавление счетчика. Возвращает false - если невозможно добавить
	bool add(int value) {
		size_t new_size = lcm(value, 32);
		if (size != new_size && size % new_size != 0) {
			// Не входит кратно
			return false;
		}
		for (uint32_t i = 0; i != size; i += value) {
			bm[i >> 5] ^= (1 << (i & 31));
		}
		return true;
	}

	// Перенос в другой счетчик
	void move(cnt_t& c) {
		if (c.bm != NULL) free(c.bm);
		c.bm = bm;
		c.cur = cur;
		c.end = end;
		c.size = size;
		bm = NULL;
	}

	// Занято памяти, байт
	uint32_t total() {
		return size / 8;
	}

	// Следующие 32 бита (лампочки)
	uint32_t next() {
		if (cur == end) cur = bm;
		return *(cur++);
	}
};


int main(int argc, char**argv)
{
	// Считывание задания
	ifstream in("input.txt");
	int N, K;
	in >> N >> K;
	bool P[51] = { 0 };
	for (int i = 0; i < K; i++) {
		int v;
		in >> v;
		P[v] = !P[v];
	}
	// Распределение по счетчикам (для каждого mp свой счетчик)
	vector<cnt_t> counters;
	map<int, int> mp_idx;
	counters.reserve(12);
	int k_init = 0;
	for (int i = 50; i > 0; i--) {
		if (P[i]) {
			k_init = 1 - k_init;
			int mp = max_prime(i);
			if (mp < 11) mp = 11; // все маленькие в один
			map<int, int>::iterator it = mp_idx.find(mp);
			if (it != mp_idx.end()) { // Счетчик уже есть
				if (!counters[it->second].clue(i)) {
					it = mp_idx.end(); // Не склеилось
				} else {
#ifdef _DEBUG
					cout << endl << i << "->" << it->second;
#endif
				}
			}
			if(it == mp_idx.end()) { // Добавление счетчика
				counters.push_back(cnt_t());
				counters[counters.size() - 1].init(i);
				mp_idx[mp] = counters.size() - 1;
#ifdef _DEBUG
				cout << endl << i << "->" << mp_idx[mp];
#endif
			}
		}
	}
	int total = 0;
	for (int i = 0; i < counters.size(); i++) {
		total += counters[i].total();
	}
#ifdef _DEBUG
	cout << endl << "memory " << total;
#endif
	// Склеивание счетчиков
	int prev = 0;
	while(prev != counters.size()) {
		prev = counters.size();
		// поиск минимального
		int add_idx = prev - 1;
		int size_test = counters[add_idx].total();
		for (int i = 0; i < prev - 2; i++) {
			if(size_test > counters[i].total()) {
				size_test = counters[i].total();
				add_idx = i;
			}
		}
		int64_t min = MAX_MEMORY - total + size_test;
		int min_idx = prev;
		// Поиск наименьшего размера после склеивания
		for (int i = 0; i < prev; i++) {
			if (i == add_idx) continue;
			int64_t new_size = lcm(size_test, counters[i].total());
			if(min > new_size) {
				min = new_size;
				min_idx = i;
			}
		}
		if(min_idx != prev) {
			total += (int)min - size_test;
			if (total > MAX_MEMORY) break;
			if(counters[min_idx].clue(counters[add_idx])) {
#ifdef _DEBUG
				cout << endl << "[" << add_idx << "] => [" << min_idx << "] " << "memory " << total;
#endif
				if(add_idx != prev - 1) { // непоследний
					counters[prev - 1].move(counters[add_idx]);
				}
				counters.pop_back();
			}
		}
	}
	cout << endl << "counters " << counters.size() << " memory " << total / 1024 << "Kb";
	// Для подсчета единичных бит в байте
	int bit_cnt[256] = { 0 };
	for (int i = 0; i < 256; i++) {
		int n = i;
		while (n != 0) {
			bit_cnt[i]++;
			n &= (n - 1);
		}
	}
	// Расчет
	int res = 0;
	cnt_t* start = &counters[0];
	cnt_t* end = start + counters.size();
	int next = 0;
	register uint32_t k = k_init;
	while (true) { // Самый тяжелый цикл
		// Очередная порция лампочек
		for (cnt_t* c = start; c < end; c++) {
			k ^= c->next();
		}
		next += 32;
		// подсчет лампочек (бит)
		if(next <= N) {
			res += bit_cnt[k & 0xFF];
			k >>= 8;
			res += bit_cnt[k & 0xFF];
			k >>= 8;
			res += bit_cnt[k & 0xFF];
			k >>= 8;
			res += bit_cnt[k];
			k = 0;
		} else {
			for (int i = next - 32; i <= N; i++) {
				if ((k & 1) != 0) res++;
				k >>= 1;
			}
			break;
		}
	}
	// Вывод результата
	ofstream out("output.txt");
	out << res << endl;
	out.close();
	cout << endl << "time " << clock() << endl;
	cout << "Result " << res << endl;
	return 0;
}