1 #include <cstdio>
2 #include <iostream>
3 #include <algorithm>
4 using namespace std;
5 int i,n,m,k[12];
6 long long d,x,y,ans;
7 void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
8 {
9 if (!b) d=a,x=1,y=0;
10 else exgcd(b,a%b,d,y,x),y=y-x*(a/b);
11 }
12 long long gcd(long long x,long long y) { return y?gcd(y,x%y):x; }
13 long long lcm(long long x,long long y) { return x*y/gcd(x,y); }
14 void dfs(int t,long long tot1,long long tot2,long long x1,long long x2,long long w)
15 {
16 if (x1>n||x2>n) return;
17 if (t>m)
18 {
19 if (tot1==0||tot2==0) return;
20 exgcd(x1,x2,d,x,y);
21 if (d<0) x=-x,y=-y,d=-d;
22 if (d>1) return;
23 x=(x%x2+x2)%x2;
24 ans+=w*((1LL*n/x1-x)/x2+(x1*x<=n));
25 return;
26 }
27 dfs(t+1,tot1,tot2,x1,x2,w);
28 dfs(t+1,tot1+1,tot2,lcm(x1,k[t]),x2,-w);
29 dfs(t+1,tot1,tot2+1,x1,lcm(x2,k[t]),-w);
30 }
31 int main()
32 {
33 freopen("sazetak.in","r",stdin);
34 freopen("sazetak.out","w",stdout);
35 scanf("%d%d",&n,&m);
36 for (int i=1;i<=m;i++) scanf("%d",&k[i]);
37 k[++m]=n;
38 dfs(1,0,0,1,1,1);
39 printf("%lld",ans);
40 return 0;
41 }