#include <algorithm>
#include <stdio.h>
#include <vector>

#define ll long long
#define pb push_back

using namespace std;

ll n, m, sol;
ll d1[32];
vector <ll> d2;

ll cmmmc[1 << 21];

inline ll gcd(ll a, ll b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

int main()
{
	freopen("light2.in", "r", stdin);
	freopen("light2.out", "w", stdout);

    scanf("%lld", &m);

    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d", &d1[i]);

    sort(d1, d1 + n);
    int p;
    for (p = 1; p < n; p++)
        if (d1[p] != d1[p - 1])
            d2.pb(d1[p - 1]);
        else p++;
    if (p == n)
        d2.pb(d1[n - 1]);
    n = d2.size();

    cmmmc[0] = 1;
    for (int conf = 1; conf < (1 << (n - 1)); conf++)
    {
        ll st = -1, el = 0;
        cmmmc[conf] = 1;
        for (int i = 0; i < n - 1; i++)
            if (conf & (1 << i))
            {
                cmmmc[conf] = cmmmc[conf - (1 << i)] / gcd(cmmmc[conf - (1 << i)], d2[i]) * d2[i];
                cmmmc[conf] = min(cmmmc[conf], m + 1);

                break;
            }

        for (int i = 0; i < n; i++)
            if (conf & (1 << i))
            {
                el++;

                if (st == 1)
                    st = -1;
                else st = 1;
            }

        sol += st * (m / cmmmc[conf]) * (1 << (el - 1));
    }

    for (int conf = 0; conf < (1 << (n - 1)); conf++)
    {
        ll st = 1, el = 1;
        ll c = d2[n - 1];

        c = cmmmc[conf] / gcd(cmmmc[conf], c) * c;
        c = min(c, m + 1);

        for (int i = 0; i < n; i++)
            if (conf & (1 << i))
            {
                el++;

                if (st == 1)
                    st = -1;
                else st = 1;
            }

        sol += st * (m / c) * (1 << (el - 1));
    }

    printf("%lld\n", sol);

	fclose(stdin);
	fclose(stdout);
    return 0;
}