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

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

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

LL afla(LL a, int b) {
    LL cmc = gcd(a, b);
    long double x = a / cmc;

    if(x > rad && b > rad) return 0;

    LL fin = (LL)x * b;

    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-1)); 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], 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]);
    }

    rad = (double)sqrt((long double)N);

    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 > 0) {
              nrb ++;
              p = p - LSB(p);
         }

         if(i < (1 << (K-1))) {

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

         }
         else {
              p = i;
              nrb = 0;
              LL cmmc = 1;
              while(p > 0) {
                   nrb ++;
                   j = bin( LSB(p) );
                   cmmc = afla(cmmc, D[j+1]);
                   p = p - LSB(p);
              }

              p = i - (1 << (K - j));

              cmmc = afla(D[j+1], cmmmc[p]);

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

    }

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