526互联

容斥原理应用Acwing890借鉴题解

发布时间 2023-09-21 22:18:29作者: potential-star

参考文献

简单的容斥原理介绍请看下图：
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的值来选择是”+”还是“-”

代码如下：

#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;
}