【UVa#10325】The Lottery

青旅半醒 2023-06-05 08:54 102阅读 0赞

# Description #

[UVa\#10325][UVa_10325]

给定n和m个数，求1~n中不被这m个数中任意一个数整除的数的个数

# Solution #

容斥原理

假设现在求1~n中被这a，b中任意一个数整除的数的个数

这个区间中能被a整除的数的个数是$\\lfloor\\frac\{n\}\{a\}\\rfloor$

同理，能被b整除的数的个数是$\\lfloor\\frac\{n\}\{b\}\\rfloor$

那么被a，b两个数中任意一个数整除的数有$\\lfloor\\frac\{n\}\{a\}\\rfloor+\\lfloor\\frac\{n\}\{b\}\\rfloor-\\lfloor\\frac\{n\}\{lcm(a,b)\}\\rfloor$

这是因为a，b的公倍数会被多算一次，a,b的公倍数一共有$\\lfloor\\frac\{n\}\{lcm(a,b)\}\\rfloor$个

推广到m个数上

被这m个数中的任意一个数整数的数的个数就是

被任意一个数整除的个数-被任意两个数的公倍数整除的个数+被任意三个数的公倍数整除的数的个数-……

那么我们枚举一下，然后利用容斥原理就可以了

最后用总数减去结果就是答案了

时间复杂度$O(2^\{m\}\\times m)$

# Code #

#include <bits/stdc++.h>
    namespace shl {
        typedef long long ll;
        int a[20];
        int n, m;
        ll ans;
        ll gcd(ll a, ll b) {
            if (!b) return a;
            return gcd(b, a % b);
        }
        ll lcm(ll a, ll b) {
            return a / gcd(a, b) * b;
        }
        int main() {
            while (~scanf("%d%d", &n, &m)) {
                memset(a, 0, sizeof(a));
                ans = n;
                int num;
                for (register int i = 1; i <= m; ++i)
                    scanf("%d", &a[i]);
                int full = 1 << m;
                for (register int i = 1; i < full; ++i) {
                    num = 0;
                    ll sum = 1ll;
                    for (register int j = 0; j < m; ++j)
                        if (i & (1 << j)) {
                            num++;
                            sum = lcm(sum, a[j + 1]);
                        }
                    if (num & 1) ans -= n / sum;
                    else ans += n / sum;
                }
                printf("%lld\n", ans);
            }
            return 0;
        }
    };
    int main() {
        shl :: main();
        return 0;
    }

$\\lfloor\\frac\{n\}\{a\}\\rfloor$

转载于:https://www.cnblogs.com/shl-blog/p/11382695.html

[UVa_10325]: https://www.luogu.org/problem/UVA10325