首页 > 代码库 > BZOJ 1853 SCOI2010 幸运数字 容斥原理+DFS
BZOJ 1853 SCOI2010 幸运数字 容斥原理+DFS
题目大意:求[l,r]区间内有多少个数是只由6和8组成的数的倍数
同2393 链接:http://blog.csdn.net/popoqqq/article/details/41807333
此题数据强力了一些 由于r<=10^10 所以计算LCM的时候会爆long long
于是我们可以用double求出LCM的近似值与r进行比较 如果小于r再取精确值进行计算
此外就是搜索的时候要从大到小搜 从小到大会TLE
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 2050 using namespace std; typedef long long ll; ll l,r,a[M],b[M],ans; bool v[M]; void DFS1(ll now) { if(now>r) return ; a[++a[0]]=now; DFS1(now*10+6); DFS1(now*10+8); } void DFS2(int pos=b[0],int flag=-1,ll now=1) { if(!pos) { if(now^1) ans+=(r/now-(l-1)/now)*flag; return ; } DFS2(pos-1,flag,now); ll temp=b[pos]/__gcd(now,b[pos]); if((long double)temp*now>r) return ; DFS2(pos-1,-flag,temp*now); } int main() { int i,j; cin>>l>>r; DFS1(6);DFS1(8); sort(a+1,a+a[0]+1); for(i=1;a[i];i++) if(!v[i]) { b[++b[0]]=a[i]; for(j=i+1;a[j];j++) if(a[j]%a[i]==0) v[j]=1; } DFS2(); cout<<ans<<endl; return 0; }
BZOJ 1853 SCOI2010 幸运数字 容斥原理+DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。