#include<fstream>
#include<iostream>
using namespace std;
long long n,k,v[25],s,mx=1,ok=1;
ofstream out("light2.out");
bool y[1000002];
void gert()
{int i,h,j,mec,sw,r;
i=n/1000000;
if(i)
	{r=n%1000000;
	for(j=1;j<=r;j++)
	{mec=0;
	for(h=1;h<=k;h++)
		if(v[h]&&j%v[h]==0)
			mec++;
	if(mec%2==1)
		s++;
	}
	sw=s;
	for(;j<=1000000;j++)
	{mec=0;
	for(h=1;h<=k;h++)
		if(v[h]&&j%v[h]==0)
			mec++;
	if(mec%2==1)
		s++;
	}
	s=s*i+sw;
	}
else
for(j=1;j<=n;j++)
	{mec=0;
	for(h=1;h<=k;h++)
		if(v[h]&&j%v[h]==0)
			mec++;
	if(mec%2==1)
		s++;
	}
}
int cmmmc(long long a,long long b)
{long long r,x,y;
x=a;y=b;
while(b!=0)
	{r=a % b;a=b;b=r;}
return x*y/a;
}
long long min(long long a,long long b)
{if(a<b)	return a;return b;}
/*void numara()
{long long i,j,r,s2;
j=n-mx;
if(j>0)
	{r=n/mx;
	j=n%mx;
	for(i=1;i<=j;i++)
		if(y[i])
			s++;
	s2=s;
	for(;i<=mx;i++)
		if(y[i])
			s++;
	s=s*r+s2;
	}
else
	{for(i=1;i<=n;i++)
		if(y[i])
			s++;
	}
}
void doit()
{long long i,j,d;
for(i=1;i<=k;i++)
	if(v[i])
	{d=min(n,mx);
	for(j=v[i];j<=d;j+=v[i])
		{if(y[j]) y[j]=0;
		else	y[j]=1;}
	}
}*/
void citire()
{int i,j;
ifstream in("light2.in");
in>>n>>k;
for(i=1;i<=k;i++)
	{in>>v[i];
	if(ok) mx=cmmmc(mx,v[i]);
	if(mx>1000000)
		ok=0,mx=n;
	}
for(i=1;i<k;i++)
	for(j=i+1;j<=k;j++)
		if(v[i]==v[j])
			{v[i]=0;
			v[j]=0;
			break;
			}
mx=min(mx,1000000);
in.close();
}
int main()
{citire();
/*doit();
numara();*/
gert();
out<<s;out.close();
return 0;
}