玲珑学院 1138 震惊，99%+的中国人都会算错的问题 【容斥】【技巧】

发表于 | 更新于 | 分类于

题目大意：

一开始编号1-n中的所有数字都为0，告诉你m个数字，将所有标号为这m个数字的倍数的值都^1，问最后有多少个数字值为1。

解题思路：

考虑到n的范围很大，而m最多只有15个值，我们用容斥来做。

因为每次都是编号满足条件的值与1异或，所以值一直在1、0之间变动，因此不能像之前的找倍数那样直接加减。

(比如n=10，m=2，k1 k2分别为2 3时，编号6的值最终结果为0)

换个思路想就是这个格子是否被统计了奇数次(奇数次为1偶数次为0)，按二进制考虑，所以满足$A \times B$的倍数时就应在总数中 $- 2 \times 数量$，当满足$A \times B \times C$的倍数时就$ + 2^ 2 \times 数量$，这样…… 即$± 2 ^{(位数-1)} \times 数量$。

Mycode：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX = 10005;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;

int t, m;
LL a[20], ans, n;
LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a % b);
}
LL lcm(LL a, LL b)
{
    return a / gcd(a, b) * b;
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        ans = 0;
        scanf("%lld%d",&n,&m);
        for(int i = 0; i < m; ++i)
            scanf("%lld",&a[i]);
        for(int i = 1; i < (1 << m); ++i)
        {
            LL mul = 1;
            int bits = 0;
            for(int j = 0; j < m; ++j)
            {
                if(i & (1 << j))
                {
                    bits++;
                    mul = lcm(mul, a[j]);
                    if(mul > n) break;
                }
            }
            if(bits & 1)
                ans += n / mul * (1 << (bits - 1));
            else
                ans -= n / mul * (1 << (bits - 1));
        }
        printf("%lld\n", ans);
    }
    return 0;
}
Donate comment here
0%