#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;
}

int bin(int val) {
    int ls = 0, ld = 22;
    while(ls <= ld) {
         int mij = (ls + ld) >> 1;
         if(put[mij] > val) {
              ld = mij - 1;
         }
         else if(put[mij] < val) {
              ls = mij + 1;
         }
         else {
              return mij;
         }
    }
}

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

    for(i=1; i<(1 << K); i++) {
         p = i;
         q = i - LSB(i);
         j = bin( LSB(i) );

         if(q == 0) {
              cmmmc[i] = D[j+1];
         }
         else {
              cmmmc[i] = afla(cmmmc[q], (LL)D[j+1]);
         }
    }
}

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, nrb;

    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;

    calc_put();

    afla_cmmmc();

    for(i=1; i<(1 << K); i++) {
         p = i; nrb = 0;
         while(p) {
              nrb ++;
              p = p - LSB(p);
         }

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

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