容斥原理应用Acwing890借鉴题解
title: 容斥原理应用Acwing890借鉴题解
categories:
- ICPC
tags:
- null
abbrlink: 3c2dfe70
date: 2024-01-11 00:00:00
参考文献
简单的容斥原理介绍请看下图:
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;
}
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 爱飞鱼的blog!