Cod sursa(job #2241017)

Utilizator PopoviciRobertPopovici Robert PopoviciRobert Data 14 septembrie 2018 16:52:18
Problema Light2 Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll INF = 1e18;
const int MAXK = 21;

inline ll gcd(ll a, ll b) {
    ll r;
    while(b > 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int d[MAXK], k;
ll dp[1 << MAXK], n;

void bkt(int bit, int conf, ll val) {
    if(bit == k) {
        dp[conf] = n / val;
    }
    else {
        bkt(bit + 1, conf, val);
        val /= gcd(d[bit], val);
        if(INF / val >= d[bit])
            bkt(bit + 1, conf ^ (1 << bit), val * d[bit]);
    }
}

int main() {
    FILE *fi, *fout;
    int i;
    fi = fopen("light2.in" ,"r");
    fout = fopen("light2.out" ,"w");
    fscanf(fi,"%lld %d " ,&n,&k);
    for(i = 0; i < k; i++) {
        fscanf(fi,"%d " ,&d[i]);
    }
    bkt(0, 0, 1);
    for(i = 0; i < k; i++) {
        for(int conf = (1 << k) - 1; conf > 0; conf--) {
            if(conf & (1 << i)) {
                dp[conf ^ (1 << i)] -= dp[conf];
            }
        }
    }
    ll ans = 0;
    for(int conf = 1; conf < (1 << k); conf++) {
        if(__builtin_popcount(conf) & 1) {
            ans += dp[conf];
        }
    }
    fprintf(fout,"%lld" ,ans);
    fclose(fi);
    fclose(fout);
    return 0;
}