BZOJ 1853 【Scoi2010】 幸运数字

Description

在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认 为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“幸运号码”总是太少 了,比如在[1,100]的区间内就只有6个(6,8,66,68,86,88),于是他又定义了一种“近似幸运号码”。lxhgww规定,凡是“幸运号 码”的倍数都是“近似幸运号码”,当然,任何的“幸运号码”也都是“近似幸运号码”,比如12,16,666都是“近似幸运号码”。 现在lxhgww想知道在一段闭区间[a, b]内,“近似幸运号码”的个数。

Input

输入数据是一行,包括2个数字a和b

Output

输出数据是一行,包括1个数字,表示在闭区间[a, b]内“近似幸运号码”的个数

HINT

【数据范围】
对于$30\%$的数据,保证$1 \leqslant a \leqslant b \leqslant1000000$
对于$100\%$的数据,保证$1 \leqslant a \leqslant b \leqslant 10000000000$

 
  这道题一开始我还以为需要用到什么神奇的数学推导,或者一些什么奇妙的数学公式,然后看了题解之后发现是一道搜索题……
  一个非常显然的事实就是幸运号码不会太多。把表打出来,就会发现在$10^{10}$以内的幸运数只有$2000$多一点……
  这个时候一个非常显然的想法就是对这些数进行容斥,即加上每个数的倍数个数,减去两个数的倍数个数,加上三个的,……以此类推。
  这样的复杂度显然是不对的,理论上可达$O(2^x)$,其中$x$为幸运数个数。但是由于多个数的倍数不能超过右边界,就可以减一大刀,实际复杂度低了不知道多少。
  但是这样任然不够。我们还可以对幸运数进行处理,将其中是另外的幸运数的倍数的数给去掉。这样可以将需要考虑的数的个数减掉一半左右。
  最后还有一个小优化,那就是将最后需要处理的幸运数按从大到小排好序。这样可以让乘积尽早变得更大,可以减掉许多不必要的计算。
  加了上述优化,就差不多可以$AC$了。
  下面贴代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 10010 using namespace std;
typedef long long llg; int la,lb,ci;
llg now,ans,mi[15],l,r;
llg a[maxn],b[maxn]; void search(int d){
if(now>r) return;
llg xx=now;
now=xx+6*mi[d]; search(d+1);
now=xx+8*mi[d]; search(d+1);
if(xx) a[++la]=xx; now=xx;
} llg gcd(llg a,llg b){
llg r=a%b;
while(r) a=b,b=r,r=a%b;
return b;
} void dfs(int j){
if(j==lb+1){
if(!ci) return;
if(ci&1) ans+=r/now-(l-1)/now;
else ans-=r/now-(l-1)/now;
return;
}
dfs(j+1); llg xx=now; ci++;
now=xx/gcd(xx,b[j]);
if((double)now*b[j]<=r){
now*=b[j];
if(now<=r) dfs(j+1);
}
ci--; now=xx;
} int main(){
File("a");
mi[0]=1;
for(int i=1;i<=10;i++) mi[i]=mi[i-1]*10;
scanf("%lld %lld",&l,&r);
search(0); sort(a+1,a+la+1);
for(int i=1;i<=la;i++){
b[++lb]=a[i];
for(int j=1;j<lb;j++)
if(a[i]%b[j]==0){lb--; break;}
}
for(int i=1;i<=lb/2;i++) swap(b[i],b[lb-i+1]);
now=1; dfs(1);
printf("%lld",ans);
return 0;
}
上一篇:python ‘DIRS‘: [os.path.join(BASE_DIR, ‘templates‘)] NameError: name ‘os‘ is not defined


下一篇:BZOJ 3669 【NOI2014】 魔法森林