AcWing 890. 能被整除的數
來自大佬的博文
ttps://img-blog.csdnimg.cn/20210221211724332.png)
這是一道典型的容斥問題，凡是個數為奇數的就系數為正，然后偶數為負
y總的視頻講的很清楚首先我們想辦法把n個數的的倍數求出來求出他們的個數，然后進行一個容斥運算，為什么要用二進制呢，因為1到2m-1是0位到m-1位的0,1的全排列，所以我們參考這部分的知識
#include<iostream>
using namespace std;
const int N=20;
typedef long long LL;
int p[N];
int main(void)
{
int n,m,res=0;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++) cin>>p[i];
for(int i=1;i<1<<m;i++)
{
int t=1,cnt=0;
for(int j=0;j<m;j++)
{
if(i>>j&1)
{
cnt++;
if((LL)t*p[j]>n)
{
t=0;
break;
}
t*=p[j];
}
}
if(t)
{
if(cnt&1) res+=n/t;
else
res-=n/t;
// cout<<res<<endl;
}
}
cout<<res;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/262126.html
標籤：其他
上一篇：設計模式-原型模式（簡歷復印）