首页 > 代码库 > BZOJ1853 SCOI2010 幸运数字 DFS+容斥原理
BZOJ1853 SCOI2010 幸运数字 DFS+容斥原理
题意：求[a,b]中含有6 8或因子含有6 8的数的个数
题解：
我们用容斥的思想，先求出1->b的方案数，再减去1->a-1的方案数
首先我们一遍DFS求出所有由6和8组成的数的数量
然后将搜索得到的所有数排序，如果存在a%b==0，那就把a给删了（打个标记）。
由于得到的数非常少，所以我们可以枚举乘积可能得到的数字num，那么就会有N/num个数含有num这个因子，因此ans+=N/num。
两个细节上的问题：
1.如果我们当前枚举得到的乘积为a，需要乘下一个数b搜索到下一层时，只需要传递lcm(a,b)即可
2.枚举得到的数一定会爆long long，要是有闲心可以去写高精……我上网搜了一下发现都是用double判精度之类很神奇的方法（至少我是没看懂……）。由于我懒到爆了，所以直接用自然溢出——如果枚举得到的数now<0，那肯定是发生自然溢出了，但问题在于如果第32位溢出后是0，那么now>0这样就得到了错解，但是数据非常的友善，我就这样AC了……
#include <cmath>#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;#define lcm(a,b) (a*b/gcd(max(a,b),min(a,b)))#define ll long longconst int MAXN=100000;ll a,b,cnt,num[MAXN],ans,tot;bool flag[MAXN];ll gcd(ll a,ll b){ return (!b?a:gcd(b,a%b));}bool cmp(ll a,ll b){ return a>b;}void DFS1(ll now,ll N){ if(now>N) return; DFS1(now*10+6,N),DFS1(now*10+8,N); if(now) num[++cnt]=now;}void DFS2(ll now,int deep,int c,ll N){ if(deep==cnt || now>N || now<0) return;//now<0 =>自然溢出 =>可行性剪枝 ll ret=0,type=(deep%2?1:-1); if(now!=1) ans+=type*N/now; for(int i=c;i<=cnt;i++) if(!flag[i]) DFS2(lcm(now,num[i]),deep+1,i+1,N);}ll Slove(ll N){ ans=cnt=0; memset(flag,0,sizeof(flag)); DFS1(0,N); sort(num+1,num+cnt+1,cmp); for(int i=1;i<=cnt;i++) for(int j=i+1;j<=cnt;j++) if(!(num[i]%num[j])){ flag[i]=1; break; } DFS2(1,0,1,N); return ans;}int main(){ cin >> a >> b; cout << Slove(b)-Slove(a-1) << endl; return 0;}
BZOJ1853 SCOI2010 幸运数字 DFS+容斥原理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。