#include <cstdio>
#include <algorithm>

using namespace std;
long long v[30];
int p[30];
long long cmmdc (long long a,long long b){
    long long r;
    while (b){
        r=a%b;
        a=b;
        b=r;
    }
    return a;
}
int main()
{
    FILE *fin=fopen ("light2.in","r");
    FILE *fout=fopen ("light2.out","w");
    int k,poz,lc,i,fact;
    long long sol,nr,n;
    fscanf (fin,"%lld%d",&n,&k);
    for (i=1;i<=k;i++)
        fscanf (fin,"%d",&v[i]);
    sort (v+1,v+k+1);
    poz=0;
    lc=1;
    for (i=1;i<=k;i++){
        if (v[i]!=v[i+1]){
            if (lc%2==1)
                v[++poz]=v[i];
            lc=1;
        }
        else lc++;
    }
    k=poz;
    sol=0;
    // facem un fel de pinex
    while (v[0]==0){
        i=k;
        while (p[i]){
            p[i]--;
            i--;
        }
        p[i]=1;
        if (i==0)
            break;
        nr=1;
        fact=0;
        for (i=1;i<=k;i++){
            if (p[i]){
                nr=nr*v[i]/cmmdc(nr,v[i]);
                fact++;
            }
            if (nr>n)
                break;
        }
        if (i<=k)
            continue;
        if (fact%2==1)
            sol=sol+(1<<(fact-1))*n/nr;
        else sol=sol-(1<<(fact-1))*n/nr; // i am adunat de mai mult de n/nr ori
        // i am adunat la fiecare factor la care am fost + sumele cu factori impari
    }
    fprintf (fout,"%lld",sol);
    return 0;
}