UVA - 10325 The Lottery

10325.cpp

#include <bits/stdc++.h>
using namespace std;

template <class T> int size(const T &x) {return x.size();}
template <class T> T mod(T a, T b) { return (b + (a % b)) % b;}

#define F first
#define S second
#define PB push_back
#define endl '\n'
#define rep(i, a, b) for(__typeof(a) i=a; i<(b); i++)
#define iter(it, c) for(__typeof((c).begin()) it=(c).begin(); \
 it != (c).end(); it++)

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;

const int INF = ~(1 << 31);
const double EPS = 1e-9;
const double PI = acos(-1);

const ll MX = 2e7 + 7;
bitset<MX> sieve;
vi primes;

int power_set(vi &A, int n) {
    ll sum = 0;
    for(int msk=1; msk<(1<<A.size()); msk++) {

        ll lcm = 1; int bits = 0;
        for(int i=0; i<A.size(); i++) {
            if(msk & (1<<i)) {
                ++bits;
                lcm = lcm * (A[i] / __gcd(lcm, (ll)A[i]));
            }
        }

        if(bits & 1) sum += n / lcm;
        else sum -= n / lcm;
    }

    return sum;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, r;
    while(cin >> r >> n) {
        vi A(n);
        for(int &i : A) cin >> i;

        cout << r - power_set(A, r) << endl;
    }
    return 0;
}