#include <fstream>

using namespace std;

ifstream f("light2.in");
ofstream g("light2.out");

const int KMAX = 25;

long long N;

int K;

long long ans = 0;

int d[KMAX], Comb[KMAX][KMAX], dp[KMAX];

static inline void Read ()
{
    f.tie(NULL);

    f >> N >> K;

    for(int i = 1; i <= K; ++i)
        f >> d[i];

    return;
}

static inline long long cmmdc (long long a, long long b)
{
    long long r = 0;

    while(b)
    {
        r = a % b;

        a = b;

        b = r;
    }

    return a;
}

static inline void Precalculation ()
{
    Comb[1][1] = 1;

    for(int i = 2; i <= K; ++i)
    {
        Comb[i][1] = i;

        for(int j = 2; j <= i; ++j)
            Comb[i][j] = Comb[i - 1][j - 1] + Comb[i - 1][j];
    }

    for(int i = 1; i <= K; ++i)
        for(int j = 1; j <= i; j += 2) /// Doar cele cu indice impar sunt de adunat;
            dp[i] += Comb[i][j];

    return;
}

int main()
{
    Read();

    Precalculation();

    for(int i = 1; i <= (1 << K); ++i)
    {
        int cnt = 0;

        long long prod = 1;

        for(int j = 0; j < K; ++j)
            if(i & (1 << j))
            {
                ++cnt;

                prod = 1LL * (prod * d[j + 1]) / (1LL * cmmdc(prod, d[j + 1]));

                if(prod > N)
                    break;
            }

        if(prod <= N)
        {
            /// PINEX:
            long long Elem = 1LL * dp[cnt];
            Elem *= 1LL * (N / prod);

            if(cnt % 2 ==1)
                ans += 1LL * Elem;
            else ans -= 1LL * Elem;
        }
    }

    g << ans << '\n';

    return 0;
}