参考文献

简单的容斥原理介绍请看下图：
QQ浏览器截图20200807160444.png
QQ浏览器截图20200807160125.png

C++ 代码

简单的容斥原理介绍请看下图：

本题思路：
将题目所给出的m个数可以看成是m位的二进制数，例如
当p[N]={2,3}时，此时会有01,10,11三种情况
而二进制的第零位表示的是p[0]上面的数字2,第1位表示p[1]上面的数字3
所以当i=1时表示只选择2的情况，当i=2（10）时,表示只选择3的情况,当i=3时,表示2和3相乘的情况
在过程中可以用标记变量t记录,可以按照t的值来选择是”+”还是“-”

代码如下：

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
#include
#include

using namespace std;

typedef long long LL;

const int N=20;
int p[N];

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0;i>p[i];

    int res=0;

    for(int i=1;i<1<>j&1)
        {
            if((LL)t*p[j]>n)
            {
                t=-1;
                break;
            }
            t*=p[j];
            ++cnt;
        }

        if(t!=-1)
        {
            if(cnt%2) res=res+n/t;
            else res=res-n/t;
        }
    }

    printf("%d",res);

    return 0;
}