Pagini recente » Cod sursa (job #935157) | Borderou de evaluare (job #2315837) | Cod sursa (job #486642) | Rezultatele filtrării | Cod sursa (job #2020492)
#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%d\n", x);
#define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXK 23
lld N;
lld d[MAXK];
int popcnt(int x) {
int rez = 0;
while(x) {
x -= x&-x;
rez++;
}
return rez;
}
lld koliko(int mask) {
vector<int> r;
for(int i = 0; i < MAXK; i++) {
if((1<<i)&mask) r.pb(d[i]);
}
int n = sz(r);
int gcd = r[0];
for(int i = 1; i < n; i++) {
gcd = __gcd(gcd, r[i]);
}
lld lcm = gcd;
for(int i = 0; i < n; i++) {
r[i]/=gcd;
lcm *= r[i];
if(lcm > N) return 0;
}
//PRINT(mask);
//PRINT(lcm);
//PRINT(N/lcm);
return N/lcm;
}
int main() {
freopen("light2.in", "r", stdin);
freopen("light2.out", "w", stdout);
scanf("%lld", &N);
int K; scanf("%d", &K);
for(int i = 0; i < K; i++) {
scanf("%lld", &d[i]);
}
lld rez = 0;
for(int i = 1; i < (1<<K); i++) {
int bitova = popcnt(i);
if(bitova == 1) rez += koliko(i);
else if(bitova%2 == 1) rez += (bitova + 1) * koliko(i);
else rez -= bitova * koliko(i);
//printf("%lld\n", rez);
}
printf("%lld", rez);
return 0;
}