#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxk 25
#define LL long long
#define LSB(x) (x&(x-1)^x)

LL N, sol = 0;
int K;
int cmmmc[(1 << 22) + 1], put[maxk];
int aux[maxk], D[maxk], bit[maxk];

LL gcd(LL a, LL b) {
    if (!b) return a;
    return gcd(b, a % b);
}

LL afla(LL a, LL b) {
    LL cmc = gcd(a, b);
    LL fin = (LL)a * b;
    fin = fin / cmc;

    //if(fin <= N)
         return fin;
    //return 0;
}

void afla_cmmmc() {
    int i, j, p, q;

    for(i=1; i<(1 << K); i++) {
         p = i;
         int nrb = 0, lstb = 0;
         for(j=1; j<=K; j++) {
              bit[K - j + 1] = p % 2;
              p = p >> 1;
         }

         for(j=K; j>=1; j--) {
              if(bit[j]) {
                   nrb ++;
                   lstb = j;
              }
         }

         if(nrb == 1) {
              cmmmc[i] = D[lstb];
         }
         else {
              cmmmc[i] = afla(cmmmc[i - (1 << (K - lstb))], (LL)D[lstb]);
         }
    }
}

void calc_put() {
    int i;
    put[0] = 1;
    for(i=1; i<=22; i++) {
         put[i] = (LL)put[i-1] * 2;
    }
}

int main() {
    FILE *f1=fopen("light2.in", "r"), *f2=fopen("light2.out", "w");
    int i, j, p, q;

    fscanf(f1, "%lld\n", &N);
    fscanf(f1, "%d\n", &K);
    for(i=1; i<=K; i++) {
         fscanf(f1, "%d", &aux[i]);
    }

    sort(aux+1, aux+K+1);

    p = 0;
    for(i=1; i<=K; i++) {
         if(aux[i] != aux[i+1]) {
              p ++;
              D[p] = aux[i];
         }
    }

    K = p;

    afla_cmmmc();

    calc_put();

    for(i=1; i<(1 << K); i++) {
         int nrb = 0; LL rez = 1;
         p = i;
         for(j=1; j<=K; j++) {
              if(p % 2 == 1) {
                   nrb ++;
              }
              p = p >> 1;
         }

         //if(ok) {
              if(nrb % 2 == 1) {
                   //cout<<" + "<<(LL)put[nrb - 1] * (N / cmmmc[i])<<endl;
                   sol += (LL)put[nrb - 1] * (N / cmmmc[i]);
              }
              else {
                   //cout<<" - "<<(LL)put[nrb - 1] * (N / cmmmc[i])<<endl;
                   sol -= (LL)put[nrb - 1] * (N / cmmmc[i]);
              }
         //}
    }

    fprintf(f2, "%lld\n", sol);
    fclose(f1); fclose(f2);
    return 0;
}