#include <algorithm>
using namespace std;

#define pb push_back
#define mp make_pair

#define MAX (1<<22)+5
#define DIM 25

int d[DIM],nrb[MAX];
long long v[MAX];
long long N,nrt;
int K,M;

void read ()
{
    int i;

    scanf ("%lld%d",&N,&K);
    for (i=1; i<=K; ++i)
        scanf ("%d",&d[i]);
}

inline int msb (int x)
{
    int i;

    for (i=0; i<K; ++i)
        if (x&(1<<i))
            return i;
    return K;
}

inline int cmmdc (int a,int b)
{
    if (!b)
        return a;
    return cmmdc (b,a%b);
}

void solve ()
{
    int stare,bite,i,j;

    for (i=1; i<K; ++i)
        if (d[i]==d[i+1])
        {
            for (j=i+2; j<=K; ++j)
                d[j-2]=d[j];
            K-=2;
        }

    v[0]=1;
    for (stare=1; stare<(1<<K); ++stare)
    {
        bite=msb (stare);
        nrb[stare]=nrb[stare>>1]+(stare&1);
        v[stare]=v[stare^(1<<bite)]*d[bite+1]/cmmdc (d[bite+1],v[stare^(1<<bite)]%d[bite+1]);
        if (nrb[stare]&1)
            nrt+=(N/v[stare])*(1<<(nrb[stare]-1));
        else
            nrt-=(N/v[stare])*(1<<(nrb[stare]-1));
    }

    printf ("%lld",nrt);
}

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

    read ();
    solve ();

    return 0;
}