#include <fstream>
#include <algorithm>

using namespace std;

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

const int KMAX = 30;

long long N, ans = 0;

int K, d[KMAX], Comb[KMAX][KMAX], dp[KMAX], Stiva[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;
}

static inline void Go (int Level, int cnt, long long prod)
{
    if(prod > N) /// In cazul in care p depaseste N, minimalizam expresia;
        prod = N + 1;

    if(Level == K)
    {
        long long Elem = (N / prod) * dp[cnt];

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

        return;
    }

    Stiva[Level] = 0;
    Go(Level + 1, cnt, prod);

    Stiva[Level] = 1;
    Go(Level + 1, cnt + 1, prod * d[Level + 1] / cmmdc(prod, d[Level + 1]));

    return;
}

int main()
{
    Read();

    Precalculation();

    if(K <= 20)
    {
        sort(d + 1, d + K + 1);
        reverse(d + 1, d + K + 1);

        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;
            }
        }
    }
    else
        Go(0, 0, 1);

    g << ans << '\n';

    return 0;
}