首页 > 代码库 > HDU 1796 How many integers can you find （状态压缩 + 容斥原理）
HDU 1796 How many integers can you find （状态压缩 + 容斥原理）
题目链接
题意 ： 给你N，然后再给M个数，让你找小于N的并且能够整除M里的任意一个数的数有多少，0不算。
思路 ：用了容斥原理 ： ans = sum{ 整除一个的数 } - sum{ 整除两个的数 } + sum{ 整除三个的数 }………………所以是奇加偶减，而整除 k 个数的数可以表示成 lcm(A1,A2,…,Ak) 的倍数的形式。所以算出最小公倍数，
//HDU 1796#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#define LL __int64using namespace std ;LL sh[12] ;LL gcd(LL a,LL b){ return b == 0 ? a : gcd(b,a%b) ;}int main(){ LL a,b ; while(~scanf("%I64d %I64d",&a,&b)) { int c ,j = 0; for(int i = 0 ; i < b ; i++) { scanf("%d",&c) ; if(c > 0 && c < a) sh[j++] = c ; } b = j; // sort(sh,sh+b); LL ans = 0 ; for(int i = 1 ; i < (1 << b) ; i++)//(1 << b)-1种情况 { LL num = 0 ,lcm = 1; for(int j = 0 ; j < b ; j++) { if(i & (1 << j)) { num ++ ; lcm = lcm*sh[j]/gcd(lcm,sh[j]) ; } } if(num & 1) ans += (a-1)/lcm ; else ans -= (a-1)/lcm ; } printf("%I64d\n",ans) ; } return 0 ;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。