#include <bits/stdc++.h>
#define maxK 23
#define ll long long
#define maxP (1 << 22) + 2
using namespace std;
int m, k, d[maxK], cfmax, lpow[maxP];
ll n, ans;
ll gcd(ll x, ll y)
{
    ll r = x % y;
    while (r)
    {
        x = y;
        y = r;
        r = x % y;
    }
    return y;
}
void read()
{
    freopen("light2.in", "r", stdin);
    scanf("%lld\n", &n);
    scanf("%d", &k);
    for (int i = 0; i < k; ++ i)
    {
        scanf("%d", &d[i]);
        lpow[1 << i] = i;
    }
}
void solve()
{
    int i, j;
    cfmax = 1 << k;
    for (i = 1; i < cfmax; ++ i)
    {
        m = i;
        ll lcm = 1;
        int nb = 0;
        while (m)
        {
            j = lpow[m ^ (m & (m - 1))];
            lcm = 1LL * lcm / gcd(lcm, 1LL * d[j]);
            lcm = 1LL * lcm * d[j];
            if (lcm > n)
                break;
            m &= (m - 1);
            ++ nb;
        }
        if (lcm <= n)
        {
            if (nb & 1)
                ans += (1LL * (n / lcm)) << (nb - 1);
            else
                ans -= (1LL * (n / lcm)) << (nb - 1);
        }
    }
}
void write()
{
    freopen("light2.out", "w", stdout);
    printf("%lld\n", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}