Bzoj 2393: Cirno的完美算数教室 容斥原理,深搜

2393: Cirno的完美算数教室

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 287  Solved: 175
[Submit][Status][Discuss]

Description

~Cirno发现了一种baka数，这种数呢~只含有2和⑨两种数字~~

现在Cirno想知道~一个区间中~~有多少个数能被baka数整除~

但是Cirno这么天才的妖精才不屑去数啦

只能依靠聪明的你咯。

 

 

Input

一行正整数L R 

( 1 < L < R < 10^10)

 

Output

一个正整数，代表所求的答案

 

Sample Input

1 100

Sample Output

58

HINT

 

Source

 题解：

容斥原理＋爆搜。

从大到小搜常数会变小  QAQ

话说“Cirno的完美算数教室”是什么鬼。。。233。。。

 #include<bits/stdc++.h>

 using namespace std;

 #define LL unsigned long long

 #define MAXN 1100

 LL cc[MAXN],L,R,lc,sum;

 bool vis[MAXN];

 LL read()

 {

     LL s=,fh=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}

     while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}

     return s*fh;

 }

 LL Gcd(LL aa,LL bb){if(bb==)return aa;else return Gcd(bb,aa%bb);}

 void dfs(LL k)

 {

     if(k>R)return;

     if(k>)cc[++lc]=k;

     dfs(k*+);

     dfs(k*+);

 }

 void dfs(LL ii,LL x,LL y,LL gs,LL lcm)

 {

     LL i,LCM;

     if(x<lcm&&y<lcm)return;

     if(gs>)

     {

         if(gs%!=)sum+=((LL)(y/lcm)-(LL)(x/lcm));

         else sum-=((LL)(y/lcm)-(LL)(x/lcm));

     }

     if((ii+)>lc)return;

     for(i=ii+;i<=lc;i++)

     {

         if(vis[i]==false)

         {

             vis[i]=true;

             LCM=lcm;

             lcm=(lcm*cc[i])/Gcd(lcm,cc[i]);

             if(gs==)lcm=cc[i];

             dfs(i,x,y,gs+,lcm);

             lcm=LCM;

             vis[i]=false;

         }

     }

 }

 LL calc(LL L,LL R)

 {

     sum=;

     memset(vis,false,sizeof(vis));

     dfs(,L-,R,,);

     return sum;

 }

 int main()

 {

     LL len,i;

     L=read();R=read();

     lc=;

     dfs();

     sort(cc+,cc+lc+);

     len=unique(cc+,cc+lc+)-(cc+);

     lc=len;

     for(i=;i<=lc/;i++)swap(cc[i],cc[lc-i+]);

     printf("%lld",calc(L,R));

     return ;

 }