Luogu P2567 [SCOI2010]幸运数字
题目描述
在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“幸运号码”总是太少了,比如在[1,100]的区间内就只有6个(6,8,66,68,86,88),于是他又定义了一种“近似幸运号码”。lxhgww规定,凡是“幸运号码”的倍数都是“近似幸运号码”,当然,任何的“幸运号码”也都是“近似幸运号码”,比如12,16,666都是“近似幸运号码”。现在lxhgww想知道在一段闭区间[a, b]内,“近似幸运号码”的个数。
对于30%的数据,保证1<=a<=b<=1000000
对于100%的数据,保证1<=a<=b<=10000000000
首先先预处理出所有幸运数字的号码,用dfs实现。
然后将互为倍数的数除去,比如6和66,有了6了就不需要考虑66了
最后剩下943个数,考虑dfs容斥每种情况,因为要计算集合内的lcm,所以这个lcm很快就可以大于r,剪枝即可。
#include<bits/stdc++.h>
#define ll unsigned long long
const int N = 10000;
int tot,n,tag[N];
ll a[N],l,r,ans;
void dfs1(long long x){
if(x>r) return;
if(x!=0)
a[++tot]=x;
dfs1(x*10+6);
dfs1(x*10+8);
}
void init(){
dfs1(0);
std::sort(a+1,a+1+tot);
n=std::unique(a+1,a+1+tot)-a-1;
for(int i=1;i<=n;++i){
if(tag[i]) continue;
for(int j=i+1;j<=n;++j){
if(a[j]%a[i]==0){
tag[j]=1;
}
}
}
tot=0;
for(int i=1;i<=n;++i){
if(tag[i]) continue;
a[++tot]=a[i];
}
n=tot;
}
ll gcd(ll a,ll b){
return !b?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
void dfs(int x,int cur,ll s){
if(s>r) return;
if(x==n){
if(s==1) return ;
if(cur) ans+=r/s-(l-1)/s;
else ans-=r/s-(l-1)/s;
return ;
}
dfs(x+1,cur^1,lcm(s,a[x+1]));
dfs(x+1,cur,s);
}
int main(){
//freopen("luckynumber.in","r",stdin);
//freopen("luckynumber.out","w",stdout);
scanf("%lld %lld",&l,&r);
init();
dfs(0,0,1);
printf("%lld\n",ans);
}
本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。
本文永久链接: http://www.mayflyyh.com/archives/444