计数(容斥)

Posted on Edited on In

题目大意：给出 m 个数 a[1],a[2],…,a[m]求 1~n 中有多少数不是 a[1],a[2],…,a[m]的倍数。

Input:

1
2
10 2
2 3

Output:

1
3

题目分析：

1
2
3
4
容斥，但是我们要把多减去的再加回来，复杂度2的m次方·log（gcd，lcm）
比如2，3，5
res + n - 2 - 3 + 2 * 3 - 5 + 2 * 5 + 3 * 5 + 2 * 3 * 5
但是用for很麻烦也很难实现，所以我们选择大法师(dfs)

代码如下：

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
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e6 + 66;

inline int read()
{
    int s(0), w(1);
    char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') w = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void put(int x)
{
    if (! x) putchar('0');
    if (x < 0) putchar('-'), x = -x;
    int num(0); char c[66];
    while (x) c[++ num] = x % 10 + 48, x /= 10;
    while (num) putchar(c[num --]);
    return (void)(putchar('\n'));
}

int a[N], v[N];

inline int gcd(int a, int b) {return ! b ? a : gcd(b, a % b);}

inline int lcm(int a, int b) {return a * b / gcd(a, b);}
/*
inline void dfs(int dep, int t, int flag)
{
    if (t > n) return;
    if (dep == m + 1) return (void)(res += n / t * flag);
    dfs(dep + 1, t, flag);
    dfs(dep + 1, lcm(t, a[dep]), -flag);
    
    return;
}
*/
inline void dfs(int t, int dep, int flag)
{
    if (t > n) return;
    if (dep == m + 1) return (void)(res += n / t * flag);
    dfs(t, dep + 1, flag);
    dfs(lcm(t, a[dep]), dep + 1, -flag);
    return;
}

signed main()
{
    int i, t, res(0);
    int n = read(), m = read();
    for (i = 1; i <= m; ++ i) a[i] = read();
    
    dfs(1, 1, 1);
    
    put(res);
    return 0;
}

以m等于3，\(a[]=2,3,5​\)为例

(1,1,1)->(1,2,1),(2,2,-1)

​ (1,2,1)->(1,3,1),(3,3,-1)

​ (1,3,1)->(1,4,1),(5,4,-1)此时\(+n-5\)

​ (3,3,-1)->(3,4,-1),(15,4,1)此时\(-3+15\)

​ (2,2,-1)->(2,3,-1),(6,3,+1)

​ (2,3,-1)->(2,4,-1),(10,4,1)此时\(-2+10\)

​ (6,3,+1)->(6,5,1),(30,4,-1)此时\(+6-30\)

综上，\[+n-5-3+15-2+10+6-30\]

一切都井然有序，天衣无缝，这个程序写得实在是太巧妙了