BZOJ1853 [Scoi2010]幸运数字 容斥原理

题意: 所有只含6与8的数叫做幸运数字，幸运数字的倍数叫做近似幸运数字，幸运数字都是近似幸运数字。 给定区间[l,r]求其中近似幸运数字个数。 1 < =l< =r< =10000000000 解析: 显然容斥，剩下的就是黑科技的问题了。 容斥的话，就是我们首先预处理出来所有的幸运数字，然后筛一遍，筛掉所有是其他幸运数字倍数的数避免重复计算。 然后就是选1个-选2个的lcm+选3个的lcm-…. 一个dfs搞定即可。 但是需要注意，，dfs内部的lcm我们不可以求出来，因为会爆long long ，是的我也不知道为什么。 所以我们需要转成double 型比较是否越界。 另外，我们筛完之后的那些数字最好按照从大到小的顺序排，如果从小到大的话常数大一点点，但就是这么一点点你就过不去，貌似是从大到小的话更能够对一些非法状态早排除吧。 代码:

;ll;ll l,r;int cnt;int n;ll lucky[N];bool ban[N];ll ans;ll gcd(ll a,ll b){while(b){ll t=b;b=a%b;a=t;}return a;}ll lcm(ll a,ll b){return a/gcd(a,b)*b; }void init(ll num){if(num>r)return;lucky[cnt++]=num;init(num*10+6);init(num*10+8);}void dfs(int now,int chose,ll val){if(now>n){if(!chose)return;if(chose&1)ans+=r/val-(l-1)/val;else ans-=r/val-(l-1)/val;return;}dfs(now+1,chose,val);ll tmp=val/gcd(lucky[now],val);if((double)tmp*lucky[now]<=r){dfs(now+1,chose+1,tmp*lucky[now]);}}int main(){scanf(“%lld%lld”,&l,&r);init(0);cnt–;sort(lucky+1,lucky+cnt+1);for(int i=1;i<=cnt;i++){if(!ban[i]){for(int j=i+1;j<=cnt;j++){if(lucky[j]%lucky[i]==0){ban[j]=1;}}}}for(int i=1;i<=cnt;i++)if(!ban[i])lucky[++n]=lucky[i];for(int i=1;i<=(n>>1);i++)swap(lucky[i],lucky[n-i+1]);dfs(1,0,1);printf(“%lld\n”,ans);}

不是每个人都一定快乐，不是每种痛都一定要述说。