code

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.3 kB
6
Indexable
Never
#include <bits/stdc++.h>

using namespace std;

#define close(f) freopen(f".output","w",stdout)
#define open(f) freopen(f".input","r",stdin)
#define reset(x,val) memset((x),(val),sizeof(x))
#define bit(X,i) (((X)>>(i))&1)
#define pll pair<long long,long long>
#define pii pair<int,int>
#define int unsigned long long
#define maxn 22
#define MOD 1000000007
#define INF 1000000000
#define base 311
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
#define PI 3.141592653589793238462643312
#define gcd __gcd
#define lcm(x,y) (long long)(x*y)/__gcd(x,y)
#define endl "\n"
#define sqr(a) ((a)*(a))

int n,m,res = 0;
int a[maxn];

void check(int val, int cnt){
    if(cnt<2 || val>INF || m<val){
        return ;
    }
    if(cnt%2==0){
        res -= m/val;
    }else{
        res += m/val;
    }
}

void backtrack(int id, int val, int cnt){
    if(id>n){
        check(val,cnt);
        return;
    }
    if(val*a[id]<=m){
        backtrack(id+1,cnt==0?a[id]:a[id]*val,cnt+1);
    }
    backtrack(id+1,val,cnt);
}

signed main(){
    cin >> m >> n;
    for(int i = 1; i<=n; i++){
        cin >> a[i];
        res += trunc(m/a[i]);
    }
    backtrack(2,a[1],1);
    backtrack(2,0,0);
    cout << res;
    return 0;
}