#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'
using namespace std;
const int maxn = 5e6 + 3;
const int maxm = 13;
int n, m;
int k[maxm];
void read()
{
cin >> n >> m;
for (int i = 1; i <= m; i++)
cin >> k[i];
}
pair <long long, long long> extended_euclid(int a, int b)
{
if (b == 0)
return {1, 0};
int r = a % b, q = a / b;
auto res = extended_euclid(b, r);
return {res.second, res.first - 1ll * res.second * q};
}
bool dp[maxn];
void solve()
{
int ans = 0;
for (int i = 1; i <= m; i++)
if ((n - 1) % k[i] == 0)
{
ans++;
break;
}
set <long long> s;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= m; j++)
if (__gcd(k[i], k[j]) == 1)
{
long long period = 1ll * k[i] * k[j];
auto sol = extended_euclid(k[j], k[i]);
long long num = sol.second * k[i];
num %= period;
if (num < 0)
num += period;
if (num > n-2)
continue;
ans += 1 + (n-2-num) / period;
//for (long long t = num; t <= n-2; t += period)
//s.insert(t);
}
cout << ans + (int)s.size() << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
read();
solve();
}
