首页 > 代码库 > ZOJ 3233 Lucky Number --容斥原理
ZOJ 3233 Lucky Number --容斥原理
这题被出题人给活活坑了，题目居然理解错了。。哎，不想多说。
题意：给两组数，A组为幸运基数，B组为不幸运的基数，问在[low,high]区间内有多少个数：至少被A组中一个数整除，并且不被B中任意一个数整除。|A|<=15.
分析：看到A长度这么小，以及求区间内满足条件的个数问题，容易想到容斥原理，因为不被B中任意一个数整除，所以将B数组所有数取一个最小公倍数LCM，那么就变成了幸运数字都不会被这个LCM整除。
然后枚举子集，实现要将A中元素去除相互整除的情况，比如A = [2,4],这时因为被至少一个数整除就行，那么一个2就可以满足了，将4去掉。
设A1 = {区间内被a1整除的数}，A2 = {区间内被a2整除的数}，...An = {区间内被an整除的数}
那么由于：
，
然后还要处理不被LCM整除的情况，设Bi = {区间内被 i 整除的数}，则要减去的数为：
(cnt为数的个数)
所以就可以做容斥了。
一段区间[low,high]内被k整除的数的个数为: high/k-(low-1)/k
注意处理爆long long的情况
代码： (0ms)
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define ll long longusing namespace std;#define N 100007ll a[17],aa[17];ll b[504];int vis[17];ll gcd(ll a,ll b){ if(!b) return a; return gcd(b,a%b);}int calc(int S) //计算数的个数{ int cnt = 0; while(S) { if(S&1) cnt++; S >>= 1; } return cnt;}int main(){ int n,m,i,j; ll low,high; ll cnt; int S; while(scanf("%d%d%lld%lld",&n,&m,&low,&high)!=EOF) { if(n == 0 && m == 0 && low == 0 && high == 0) break; for(i=0;i<n;i++) scanf("%lld",&a[i]); for(i=0;i<m;i++) scanf("%lld",&b[i]); memset(vis,0,sizeof(vis)); sort(a,a+n); for(i=0;i<n;i++) { if(vis[i]) continue; for(j=i+1;j<n;j++) { if(vis[j]) continue; if(a[j]%a[i] == 0) //去除冗余 vis[j] = 1; } } int ka = 0; for(i=0;i<n;i++) { if(!vis[i]) aa[ka++] = a[i]; } ll lcm = 1LL; int tag = 1; for(i=0;i<m;i++) //求LCM { lcm = lcm*b[i]/(gcd(lcm,b[i])); if(lcm > high || lcm < 0) { tag = 0; break; } } if(!tag) //爆出，不管 lcm = high+1; S = (1<<ka)-1; //总状态数 ll ans = 0; for(int state=1;state<=S;state++) { int c = calc(state); int sign = (c%2?1LL:-1LL); //根据个数定符号 int tmp = state; i = 0; ll antibase = 1LL; ll base = 1LL; int flag = 1; while(i<ka) //子集 { if(tmp&1) { base = base/gcd(base,aa[i])*aa[i]; if(base > high || base < 0) { flag = 0; break; } } tmp>>=1; i++; } if(!flag) continue; ans += sign*(high/base-(low-1LL)/base); if(!tag) //LCM爆范围，不管 continue; antibase = base/(gcd(base,lcm))*lcm; ans -= sign*(high/antibase-(low-1LL)/antibase); } printf("%lld\n",ans); } return 0;}
（有发现不对的地方欢迎评论指出）
ZOJ 3233 Lucky Number --容斥原理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。