BZOJ1853：[SCOI2010]幸运数字 & BZOJ2393：Cirno的完美算数教室—

BZOJ1853：[SCOI2010]幸运数字 & BZOJ2393：Cirno的完美算数教室——题解

阅读量：5734 次

发布时间：2019-06-18

本文共 1587 字，大约阅读时间需要 5 分钟。

以前者为标准讲题。

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

这题如果不说暴力大家估计就都掉到数位dp的坑里了，然而显然我们也没法判断倍数关系是不是。

暴力搜一遍发现幸运数字很少，如果把相互为倍数的幸运数字删掉的话只有1000左右。

容斥一遍（1个数的倍数个数-2个数+3个数……）

优化：将数从大到小排序以此让lcm增长变快，然后当lcm>r时跳出。

#include#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                using namespace std;typedef long long ll;typedef long double dl;const int N=20005;const int dig1=6;const int dig2=8;ll l,r,a[N],ans,tot;inline bool cmp(ll x,ll y){ return x>y;}void init(ll x){ if(x>r)return; if(x>0)a[++tot]=x; init(x*10+dig1); init(x*10+dig2);}ll gcd(ll x,ll y){ return y?gcd(y,x%y):x;}void dfs(int now,int sum,ll k){ if(now>tot){ if(!sum)return; ans+=((sum&1)?1:-1)*(r/k-(l-1)/k); return; } dfs(now+1,sum,k); if((dl)k/gcd(k,a[now])<=(dl)r/a[now]) dfs(now+1,sum+1,k*a[now]/gcd(k,a[now]));}int main(){ scanf("%lld%lld",&l,&r); init(0);sort(a+1,a+tot+1,cmp); int tmp=0; for(int i=1;i<=tot;i++){ for(int j=i+1;j<=tot&&a[i];j++){ if(!a[j])continue; if(a[i]%a[j]==0)a[i]=0; } if(a[i])a[++tmp]=a[i]; } tot=tmp; dfs(1,0,1); printf("%lld\n",ans); return 0;}