UVA 10325 lottery 容斥原理

给出m个数，求1-n的范围内，无法整除这m个数之中任何一个数的数的个数。

设m个数为a[i], 对任意的i， n/a[i]是n中可以整除a[i]的数的个数，但是这样对于有些数重复计算了，那么就需要减去一些数，对任意两个数，设x为这两个数的lcm，那么需要减去n/lcm，然后加上任意三个数的n/lcm....... 就这样类推。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

int a[];

ll gcd(ll x, ll y) {

    return y==?x:gcd(y, x%y);

}

ll lcm(ll x, ll y) {

    return x/gcd(x, y)*y;

}

int main()

{

    int n, m;

    while(cin>>n>>m) {

        for(int i = ; i<m; i++)

            scanf("%d", &a[i]);

        ll ans = ;

        for(int i = ; i<(<<m); i++) {

            ll cnt = , mul = ;

            for(int j = ; j<m; j++) {

                if((<<j)&i) {

                    mul = lcm(mul, 1LL*a[j]);

                    cnt++;

                }

            }

            if(cnt&) {

                ans += n/mul;

            } else {

                ans -= n/mul;

            }

        }

        cout<<n-ans<<endl;

    }

    return ;

}

秒客网

UVA 10325 lottery 容斥原理

相关文章