Как уменьшить потребляемую память? Acmp Лампочки

Я написал решение задачи Лампочки, но оно не проходит по ограничению памяти, ограничение 16mb, а моя программа использует 81mb, и я не могу понять, как можно оптимизировать мой код.

У меня здесь используется комбинаторное решение задачи, подобно тому, как считается количество чисел кратных чему-либо.

Алгоритм:

N/P1 + N/P2 - N/НОК(P1, P2) * 2

N - Диапазон ли кол-во лампочек

P1, P2 - Шаг, с которым мы изменяем состояние лампочки.

Здесь два раза вычитается N/НОК(P1, P2), так как мы "включили" два раза каждую НОК(P1, P2)-тую лампочку, следовательно, мы ее выключили.

Пример:

Входные данные:

10 3
2 3 4

Решение:

Мы включили каждую вторую лампочку, эта операция ни с какой другой не пересекается, так как, это первая операция, поэтому, сейчас включено 10 / 2 = 5 лампочек.

Мы включили каждую третью лампочку, но теперь выключились некоторые лампочки, чей номер кратен 3 и 2, поэтому, нужно дважды вычесть 10 / НОК(2, 3), т. е. сейчас включено 5 + 10 / 3 - 2 * 10 / HOK(2, 3) = 6 лампочек.

Мы включили каждую четвертую лампочку, но теперь выключились некоторые лампочки, чей номер кратен 4 и 2, 4 и 3, но заново включились лампочки, чей номер кратен 4, 3 и 2, поэтому, нужно дважды вычесть 10 / НОК(2, 4) и 10 / НОК(3, 4) и четырежды прибавить 10 / НОК(2, 3, 4), т. е. сейчас включено 6 + 10 / 4 - 2 * 10 / HOK(2, 4) - 2 * 10 / HOK(3, 4) + 4 * HOK(2, 3, 4) = 4 лампочки.

0 1 0 1 0 1 0 1 0 1 - изменили состояние каждой второй
0 1 1 1 0 0 0 1 1 1 - изменили состояние каждой третьей
0 1 1 0 0 0 0 0 1 1 - изменили состояние каждой четвертой

0 - выключена
1 - включена

Дело в том, что в худшем случае, когда k == 100, массивы k и s хранят в себе 2^100 значений, и я не могу придумать, как можно оптимизировать это

Мой код:

#include <iostream>
#include <vector>

using namespace std;

int gcd(int a, int b){
    while (b != 0){
      int t = b;
      b = a % b;
      a = t;
    }

    return a;
}

int main(){
    int n, k, fi = 0, e = 1, out = 0;
    cin >> n >> k;

    std::vector<int> f, s;

    for (int i = 0; i < k; i++){
        int p, fii = 0;
        cin >> p;

        for (int j = 0; j < fi; j++){
            if (p * f[j] / gcd(p, f[j]) <= n){
                f.push_back(p * f[j] / gcd(p, f[j]));
                s.push_back(s[j] * -2);
                fii++;
            }
        }

        fi += fii + 1;
        f.push_back(p);
        s.push_back(1);
    }

    for (int i = 0; i < fi; i++) out += s[i] * (n / f[i]);

    cout << out;
}

Очень надеюсь на вашу помощь.